{x}
blog image

Minimum Moves to Reach Target Score

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 <= 109
  • 0 <= maxDoubles <= 100

Minimum Moves to Reach Target Score

This problem involves finding the minimum number of moves to reach a target score, starting from 1, using increment and double operations with a limit on the number of doubling operations.

Approach

The most efficient approach is a greedy iterative solution. We work backward from the target, prioritizing doubling when possible to minimize the number of moves.

  1. Initialization: We start with ans = 0 (representing the move count) and iterate as long as target > 1 and we have maxDoubles remaining.

  2. Odd Target: If the target is odd, we can only increment. So, we decrement target and increment ans.

  3. Even Target: If the target is even, we can double. This is more efficient than multiple increments. We halve the target (target >>= 1), decrement maxDoubles, and increment ans.

  4. Final Increments: Once either target reaches 1 or maxDoubles is exhausted, any remaining difference between target and 1 requires increment operations. We add target - 1 to ans to account for these final steps.

  5. Return: The function returns the final value of ans.

Time and Space Complexity

  • Time Complexity: O(log target). The while loop iterates at most logâ‚‚(target) times because each doubling operation halves the target. In the worst case, we perform mostly doubling operations.
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Implementation (Python)

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

Code Implementation (Java)

class Solution {
    public int minMoves(int target, int maxDoubles) {
        int ans = 0;
        while (maxDoubles > 0 && target > 1) {
            ans++;
            if (target % 2 == 1) {
                target--;
            } else {
                maxDoubles--;
                target /= 2;
            }
        }
        ans += target - 1;
        return ans;
    }
}

Code Implementation (C++)

class Solution {
public:
    int minMoves(int target, int maxDoubles) {
        int ans = 0;
        while (maxDoubles > 0 && target > 1) {
            ans++;
            if (target % 2 == 1) {
                target--;
            } else {
                maxDoubles--;
                target /= 2;
            }
        }
        ans += target - 1;
        return ans;
    }
};

Code Implementation (Go)

func minMoves(target int, maxDoubles int) int {
	ans := 0
	for maxDoubles > 0 && target > 1 {
		ans++
		if target%2 == 1 {
			target--
		} else {
			maxDoubles--
			target /= 2
		}
	}
	ans += target - 1
	return ans
}

Code Implementation (JavaScript)

/**
 * @param {number} target
 * @param {number} maxDoubles
 * @return {number}
 */
var minMoves = function(target, maxDoubles) {
    let ans = 0;
    while (maxDoubles > 0 && target > 1) {
        ans++;
        if (target % 2 === 1) {
            target--;
        } else {
            maxDoubles--;
            target = Math.floor(target / 2);
        }
    }
    ans += target - 1;
    return ans;
};

Code Implementation (TypeScript)

function minMoves(target: number, maxDoubles: number): number {
    let ans = 0;
    while (maxDoubles > 0 && target > 1) {
        ans++;
        if (target % 2 === 1) {
            target--;
        } else {
            maxDoubles--;
            target >>= 1; // Equivalent to target /= 2;
        }
    }
    ans += target - 1;
    return ans;
};

These implementations all follow the same greedy strategy, ensuring the optimal solution within the given constraints. The iterative approach avoids the recursion depth limitations and improves efficiency for very large target values.