Skip to content

2139. Minimum Moves to Reach Target Score

Description

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

Solutions

Solution 1: Backtracking + Greedy

Thinking

We start at \(1\) and may increment or double, with at most \(\textit{maxDoubles}\) doubles. Forward search interleaves the two moves. Backward, an even target with doubles left should be halved; otherwise we subtract one, because doubling is most valuable on large even values.

\(\textit{target}\) can be huge while the double budget is small, so the backward path is \(O(\min(\log \textit{target},\textit{maxDoubles}))\). With no doubles the answer is \(\textit{target}-1\).

Recurse: divide by two when even and doubles remain, otherwise subtract one.

Let's start by backtracking from the final state. Assuming the final state is \(target\), we can get the previous state of \(target\) as \(target - 1\) or \(target / 2\), depending on the parity of \(target\) and the value of \(maxDoubles\).

If \(target=1\), no operation is needed, and we can return \(0\) directly.

If \(maxDoubles=0\), we can only use the increment operation, so we need \(target-1\) operations.

If \(target\) is even and \(maxDoubles>0\), we can use the doubling operation, so we need \(1\) operation, and then recursively solve \(target/2\) and \(maxDoubles-1\).

If \(target\) is odd, we can only use the increment operation, so we need \(1\) operation, and then recursively solve \(target-1\) and \(maxDoubles\).

The time complexity is \(O(\min(\log target, maxDoubles))\), and the space complexity is \(O(\min(\log target, maxDoubles))\).

We can also change the above process to an iterative way to avoid the space overhead of recursion.

1
2
3
4
5
6
7
8
9
class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        if target == 1:
            return 0
        if maxDoubles == 0:
            return target - 1
        if target % 2 == 0 and maxDoubles:
            return 1 + self.minMoves(target >> 1, maxDoubles - 1)
        return 1 + self.minMoves(target - 1, maxDoubles)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int minMoves(int target, int maxDoubles) {
        if (target == 1) {
            return 0;
        }
        if (maxDoubles == 0) {
            return target - 1;
        }
        if (target % 2 == 0 && maxDoubles > 0) {
            return 1 + minMoves(target >> 1, maxDoubles - 1);
        }
        return 1 + minMoves(target - 1, maxDoubles);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int minMoves(int target, int maxDoubles) {
        if (target == 1) {
            return 0;
        }
        if (maxDoubles == 0) {
            return target - 1;
        }
        if (target % 2 == 0 && maxDoubles > 0) {
            return 1 + minMoves(target >> 1, maxDoubles - 1);
        }
        return 1 + minMoves(target - 1, maxDoubles);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func minMoves(target int, maxDoubles int) int {
    if target == 1 {
        return 0
    }
    if maxDoubles == 0 {
        return target - 1
    }
    if target%2 == 0 && maxDoubles > 0 {
        return 1 + minMoves(target>>1, maxDoubles-1)
    }
    return 1 + minMoves(target-1, maxDoubles)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function minMoves(target: number, maxDoubles: number): number {
    if (target === 1) {
        return 0;
    }
    if (maxDoubles === 0) {
        return target - 1;
    }
    if (target % 2 === 0 && maxDoubles) {
        return 1 + minMoves(target >> 1, maxDoubles - 1);
    }
    return 1 + minMoves(target - 1, maxDoubles);
}

Solution 2

Thinking

Solution 1 uses recursion of the same depth as the backward walk; an iterative loop removes the call stack.

While doubles remain and \(\textit{target}>1\), decrement an odd value or shift an even one; then add the leftover \(\textit{target}-1\).

The policy matches Solution 1, written as a loop.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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 >>= 1;
            }
        }
        ans += target - 1;
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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 >>= 1;
            }
        }
        ans += target - 1;
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func minMoves(target int, maxDoubles int) (ans int) {
    for maxDoubles > 0 && target > 1 {
        ans++
        if target&1 == 1 {
            target--
        } else {
            maxDoubles--
            target >>= 1
        }
    }
    ans += target - 1
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function minMoves(target: number, maxDoubles: number): number {
    let ans = 0;
    while (maxDoubles && target > 1) {
        ++ans;
        if (target & 1) {
            --target;
        } else {
            --maxDoubles;
            target >>= 1;
        }
    }
    ans += target - 1;
    return ans;
}

Comments