Problem

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 reachtarget starting with1.

Examples

Example 1

1
2
3

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

Example 2

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7

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

Solution

Method 1 – Greedy Reverse Simulation

Intuition

To minimize moves, we should use the double operation as much as possible, but only when it helps. Instead of simulating from 1 to target, we work backwards from target to 1, greedily halving when possible and decrementing otherwise.

Approach

  1. Start from target and work backwards to 1.
  2. If maxDoubles is available and target is even, halve target and use a double.
  3. If not, decrement target by 1.
  4. Count each operation as a move.
  5. Stop when target reaches 1.

Code

 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 (target > 1 && maxDoubles > 0) {
            if (target % 2 == 0) {
                target /= 2;
                maxDoubles--;
            } else {
                target--;
            }
            ans++;
        }
        return ans + (target - 1);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

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

class Solution {
    fun minMoves(target: Int, maxDoubles: Int): Int {
        var t = target
        var d = maxDoubles
        var ans = 0
        while (t > 1 && d > 0) {
            if (t % 2 == 0) {
                t /= 2
                d--
            } else {
                t--
            }
            ans++
        }
        return ans + (t - 1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        ans: int = 0
        while target > 1 and maxDoubles > 0:
            if target % 2 == 0:
                target //= 2
                maxDoubles -= 1
            else:
                target -= 1
            ans += 1
        return ans + (target - 1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn min_moves(target: i32, max_doubles: i32) -> i32 {
        let mut t = target;
        let mut d = max_doubles;
        let mut ans = 0;
        while t > 1 && d > 0 {
            if t % 2 == 0 {
                t /= 2;
                d -= 1;
            } else {
                t -= 1;
            }
            ans += 1;
        }
        ans + (t - 1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

Complexity

  • ⏰ Time complexity: O(log target), since we halve the number at each double operation.
  • 🧺 Space complexity: O(1), only a few variables are used.