Minimum Steps to Reach a Number

Consider a game where you begin with the number 1 and aim to reach a given number goal.

In each move, you may perform one of the following:

• Increase the current number by 1 (i.e., num = num + 1).
• Multiply the current number by 2 (i.e., num = 2 * num).

You can apply the increment operation as many times as you want, but the multiplication operation can only be used up to maxMultiples times.

Given two integers goal and maxMultiples, determine the minimum number of moves required to reach goal starting from 1.

Examples

Example 1:

Input: goal = 6, maxMultiples = 1
Output: 5
Explanation: Increment from 1 to 2 (1 move), multiply once to get 4 (1 move), then increment twice to reach 6 (2 moves).
Total moves = 1 + 1 + 2 = 4 moves.

Example 2:

Input: goal = 15, maxMultiples = 3
Output: 6
Explanation: Start at 1.
Increment twice to 3 (2 moves).
Multiply once to 6 (1 move).
Increment once to 7 (1 move).
Multiply once to 14 (1 move).
Increment once to 15 (1 move).
Total moves = 2 + 1 + 1 + 1 + 1 = 6 moves.

Example 3:

Input: goal = 8, maxMultiples = 2
Output: 3
Explanation: Start at 1.
Multiply once to 2 (1 move).
Multiply once to 4 (1 move).
Multiply once to 8 (1 move).
Total moves = 3 moves.

Constraints

• 1 <= goal <= 5 × 108
• 0 <= maxMultiples <= 50