9
$\begingroup$

You are given a 10-digit number: 3388766112. In each move, you can select a contiguous group of digits and increase/decrease them all by the same integer, provided that each resulting digit stays between 0 and 9 inclusive. For example, you can select the group 8766 and decrease them all by 3, resulting in 3385433112. What is the least number of moves required to bring every digit to 0? Good luck!

$\endgroup$
12
$\begingroup$

It is

4

Lower bound:

add two auxiliary 0s: 033887661120. Observe that there are 7 places where the digit changes and that each move can remove no more than two of those. Therefore at least 4 steps are required.

Upper bound:

It can be done in 4. For example, 3388766112 -> 3333211112 -> 3333222222 -> 22222222222 -> 0000000000.

$\endgroup$
1
  • $\begingroup$ That's it, you got it. Nice proof of optimality $\endgroup$ Apr 11 at 8:29
2
$\begingroup$

How about this?

Four:
3388766112
3333211112 (1)
2222211112 (2)
2222222222 (3)
0000000000 (4)

$\endgroup$
1
$\begingroup$

For completeness. Here is another optimal solution:

3388766112
0055466112 (1)
0055577222 (2)
0055555000 (3)
0000000000 (4)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.