We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Moves to Reach Target Score

Number: 1303

Difficulty: Medium

Paid? No

Companies: Amazon, Wayfair

Problem Description

You start with the integer 1 and want to reach a given target integer. In one move, you can either increment the current integer by 1 or double it. However, you can only use the double operation at most maxDoubles times. The goal is to determine the minimum number of moves required to reach the target.

Key Insights

  • When doubling is available and the target is even, doubling (or working backwards by halving) is usually optimal.
  • If the target is odd, it's best to subtract 1 (simulate the increment in reverse) to make it even.
  • Once no doubling moves remain, the remaining distance must be covered with increments.
  • Working backwards from the target to 1 simplifies the decision process, as it avoids overcounting moves.

Space and Time Complexity

Time Complexity: O(log(target)) in most cases, though in worst-case scenarios with many subtractions it can approach O(target) if doubling is exhausted quickly. Space Complexity: O(1)

Solution

We use a greedy approach working from the target backwards to 1. At each step, if we have remaining doubling moves and the target is even, we reverse a double (by halving the target) which corresponds to a double move in the forward process. If the target is odd, we subtract 1 to make it even, simulating an increment in reverse. If no doubling moves remain, we subtract 1 repeatedly until we reach 1, counting each subtraction as a move. This method ensures the number of moves is minimized.

Code Solutions

# Python solution with comments
def minMoves(target, maxDoubles):
    moves = 0
    # Process until target becomes 1
    while target > 1 and maxDoubles > 0:
        # If target is even, reverse the doubling
        if target % 2 == 0:
            target //= 2
            maxDoubles -= 1
            moves += 1
        else:
            # If target is odd, subtract 1 to even it out
            target -= 1
            moves += 1
    # After using all possible doubles, subtract one until reaching 1
    moves += (target - 1)
    return moves

# Example usage:
print(minMoves(5, 0))   # Output: 4
print(minMoves(19, 2))  # Output: 7
print(minMoves(10, 4))  # Output: 4
← Back to All Questions