Teaching Kids Programming – Minimum Moves to Reach Target Score with Constraints (Greedy Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are playing a game with integers. You start with the integer 1 and you want to reach the integer target.

In one move, you can either:
Increment the current integer by one (i.e., x = x + 1).
Double the current integer (i.e., x = 2 * x).

You can use the increment operation any number of times, however, you can only use the double operation at most maxDoubles times. Given the two integers target and maxDoubles, return the minimum number of moves needed to reach target starting with 1.

Example 1:

Input: target = 5, maxDoubles = 0
Output: 4
Explanation: Keep incrementing by 1 until you reach target.

Example 2:
Input: target = 19, maxDoubles = 2
Output: 7
Explanation: Initially, x = 1
Increment 3 times so x = 4
Double once so x = 8
Increment once so x = 9
Double again so x = 18
Increment once so x = 19

Example 3:
Input: target = 10, maxDoubles = 4
Output: 4
Explanation: Initially, x = 1
Increment once so x = 2
Double once so x = 4
Increment once so x = 5
Double again so x = 10

Constraints:
1 <= target <= 10^9
0 <= maxDoubles <= 100

Greedy Algorithm to Reach Destination

We can think of this inversely, which becomes similar to this problem: Teaching Kids Programming – Min Number of Steps to Reduce a Number to Zero. With limited number of divisions operations, we still prefer doing divisions as early as we can because it can bring down the numbers quicker e.g. 1000 to 500 is better to 10 to 5.

We can then implement this in Recursive Manner – if we used all divisions or there is none allowed left, we can only do N-1 subtractions to bring number N downto 1.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        def f(n, m):
            if n == 1:
                return 0
            if m > 0 and n & 1 == 0:
                return 1 + f(n//2, m - 1)
            if m == 0:
                return n - 1
            return 1 + f(n - 1, m)
        return f(target, maxDoubles)

class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        def f(n, m):
            if n == 1:
                return 0
            if m > 0 and n & 1 == 0:
                return 1 + f(n//2, m - 1)
            if m == 0:
                return n - 1
            return 1 + f(n - 1, m)
        return f(target, maxDoubles)

We can also implement this in iterative fashion.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        ans = 0
        while target > 1 and maxDoubles > 0:
            if target & 1 == 0:
                target >>= 1
                maxDoubles -= 1
            else:
                target -= 1
            ans += 1
        return ans + target - 1

class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        ans = 0
        while target > 1 and maxDoubles > 0:
            if target & 1 == 0:
                target >>= 1
                maxDoubles -= 1
            else:
                target -= 1
            ans += 1
        return ans + target - 1

The time complexity is O(LogN) if maxDoubles is larger or equal to LogN (enough)

Reducing Numbers to Zeros or Reach Number to N

• Teaching Kids Programming – Minimum Moves to Reach Target Score with Constraints (Greedy Algorithm)
• Teaching Kids Programming – Min Number of Steps to Reduce a Number to Zero
• Iterative and Recursion Algorithms to Compute the Number of Steps to Reduce a Number to Zero

–EOF (The Ultimate Computing & Technology Blog) —