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 <= 10^9
0 <= maxDoubles <= 100
Solution
The optimal way to get to the target would be: increase to a certain point, and double it to get to the target. So to do this, we start from the target. If it’s an odd number, use one increment operation to reduce it by 1. If it’s even and we have double operations, divide it by 2.
Time complexity: min ( m a x D o u b l e s , log ( t a r g e t ) ) \min(maxDoubles, \log(target)) min(maxDoubles,log(target))
Space complexity: o ( 1 ) o(1) o(1)
Code
class Solution:def minMoves(self, target: int, maxDoubles: int) -> int:res = 0while target > 1 and maxDoubles > 0:if target & 1 == 1:target -= 1else:target //= 2maxDoubles -= 1res += 1return res + target - 1
