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!
$\begingroup$
$\endgroup$
asked Apr 11, 2021 at 1:18
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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.
answered Apr 11, 2021 at 1:47
-
$\begingroup$ That's it, you got it. Nice proof of optimality $\endgroup$ Commented Apr 11, 2021 at 8:29
$\begingroup$
$\endgroup$
How about this?
Four:
3388766112
3333211112 (1)
2222211112 (2)
2222222222 (3)
0000000000 (4)
answered Apr 11, 2021 at 1:41
$\begingroup$
$\endgroup$
For completeness. Here is another optimal solution:
3388766112
0055466112 (1)
0055577222 (2)
0055555000 (3)
0000000000 (4)
answered Apr 11, 2021 at 8:28