# Contiguous shifts in a 10-digit number

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!

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.

• That's it, you got it. Nice proof of optimality Apr 11, 2021 at 8:29

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

For completeness. Here is another optimal solution:

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