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:
x = x + 1).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 <= 1090 <= maxDoubles <= 100In this approach, we work backward from the target to the initial value of 1. By starting from the target, we can better decide when to use the doubling operation. Our objective is to use the double operation effectively while minimizing increments.
The backward approach allows us to find a path with minimal moves by performing the inverse of the possible operations:
By applying these operations, we can ensure that we are reducing the number of moves strategically while managing the available double operations optimally.
The function iteratively reduces the target towards 1. If the target is even and we have doubles remaining, we divide the target by two. If the target is odd, we decrement it by one to convert it to an even number for possible future halving. If no doubles are left, we simply subtract increments required to reach one.
Java
C++
C
C#
JavaScript
Time Complexity: O(log target), as we either divide the number or subtract from it, reducing the problem size quickly.
Space Complexity: O(1), as no extra space is used apart from a few variables.
This approach leverages the Breadth-First Search (BFS) algorithm. We begin at position 1 and explore all possible next positions by either doubling or incrementing. The BFS ensures that we explore every state comprehensively layer by layer until we reach the target for the first time. We use a queue to keep track of the current state and the number of moves taken to reach that state.
The BFS approach naturally finds the shortest path in an unweighted graph, which aligns with finding the minimum number of moves in this problem.
The BFS solution uses a queue to perform level-order traversal through possible states. We enqueue each new state as a tuple consisting of its current value, the number of moves, and remaining double operations. BFS inherently explores states in ascending order of moves. It terminates as soon as a state matches the target, guaranteeing the solution uses the minimum moves.
Java
Time Complexity: O(target * maxDoubles), due to the potential exploration of all states within bound constraints.
Space Complexity: O(target * maxDoubles), as space could be occupied by each state derived.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(log target), as we either divide the number or subtract from it, reducing the problem size quickly. Space Complexity: O(1), as no extra space is used apart from a few variables. |
| BFS Approach | Time Complexity: O(target * maxDoubles), due to the potential exploration of all states within bound constraints. Space Complexity: O(target * maxDoubles), as space could be occupied by each state derived. |
I solved too many Leetcode problems • NeetCodeIO • 101,495 views views
Watch 9 more video solutions →Practice Minimum Moves to Reach Target Score with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor