2139. Minimum Moves to Reach Target Score

MediumGreedyMath
Leetcode Link

Problem Description

In this game, you begin with the number 1 and your goal is to reach a given target number. You can perform two types of moves: increment the current number by 1 or double it. The increment operation can be used as many times as needed, but the double operation can only be used up to a specified limit, maxDoubles. Your objective is to determine the smallest number of moves required to go from 1 to the target number, considering the limit on the number of double operations.

Intuition

Consider working backwards from the target number down to 1. If target is greater than 1 and we still have the option to double (i.e., maxDoubles is not 0), we need to decide between incrementing or doubling. To make efficient use of our moves, we should prefer doubling whenever possible because it can dramatically reduce the target number, especially when target is even. If target is odd, we have no choice but to decrement it by 1 to make it even, at which point doubling becomes an option again.

If target is even and we have the capability to double (meaning maxDoubles > 0), we should apply the doubling move—which is just a simple division by 2 of the target in the case of our reverse strategy. On the other hand, if target is already 1, we are done, and no moves are needed. The same applies if we run out of double operations (maxDoubles = 0); we will just keep decrementing the target by 1 until we reach the value of 1.

We continue this process iteratively, incrementing our move count each time we make an adjust to the target. Once we've exhausted our doubling options, or the target reaches 1, we simply add the remaining distance from target to 1 to our move count. This remaining distance will be precisely target - 1, because, at that stage, we can only increment by 1 to reach our goal.

The provided solution implements this approach iteratively, avoiding the overhead of recursion, and ensures we use the minimum moves by always choosing to double rather than increment when both moves are possible.

Learn more about Greedy and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm should you use to find a node that is close to the root of the tree?

Solution Approach

The solution can be understood as a greedy algorithm. A greedy algorithm is an approach for solving problems by making a sequence of choices, each of which simply looks like the best at the moment, without considering future consequences. In this problem, at each step, we attempt to make a move that brings us closer to 1 in the quickest way possible, given our constraint on the number of double operations available (denoted by maxDoubles).

Here's the step-by-step breakdown of the algorithm referenced in the Solution provided:

  1. Initialize a counter for the number of moves (ans) to 0.

  2. Start a while loop that continues as long as there are double operations left (maxDoubles > 0) and the target is greater than 1.

  3. Increment the move counter (ans) by 1 at each step of the loop—that's because we're making a move, either doubling or incrementing.

  4. Within the loop, check if target is odd (target % 2 == 1). If so, subtract 1 to make it even. This is a necessity since doubling is only efficient on even numbers. Note that this subtraction is effectively reversing an increment operation.

  5. If the target is even, halve the target (target >>= 1 is equivalent to target = target / 2). This represents the reverse of a doubling operation. Also, decrement the count of available double operations (maxDoubles) since we've just used one.

  6. After exiting the loop, if no double operations are left or the target has reached 1, add the difference between the target and 1 to the move counter (ans). This is because now we can only use increment operations to reach 1.

  7. Finally, return the total number of moves (ans). This value represents the minimum moves needed to reach target starting from 1 under the given constraints.

The space complexity of the algorithm is O(1), since it only requires a fixed amount of additional space (for the variables ans, target, and maxDoubles). The time complexity is O(min(log(target), maxDoubles)), which comes from the fact that doubling reduces the target by a factor of 2, and thus it would take at most log2(target) doublings to reach 1 (in a scenario with unlimited doublings), and we will make at most maxDoubles doubling moves.

This approach guarantees the minimum number of moves since:

  • Doubling when possible minimizes the number of operations by taking the largest possible reduction at each step.
  • Using increment operations only when necessary ensures that we are not wasting any double operations.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the target number 10 and a maxDoubles limit of 2.

  1. We start with target = 10 and maxDoubles = 2. Our initial move counter (ans) is 0.
  2. Since maxDoubles > 0 and target > 1, we enter the loop.
  3. target is even, so we can apply a double move. We halve target (10 becomes 5) and increment ans by 1 (so ans is now 1). We also reduce maxDoubles by 1 (now it's 1).
  4. target is now 5, which is odd. We can't double an odd number, so we subtract 1 from the target (5 becomes 4) and increment ans by 1 (ans is now 2).
  5. With target back to an even number (4), and maxDoubles > 0, we perform a double move. We halve target (4 becomes 2) and increment ans by 1 (ans is now 3), and decrement maxDoubles by 1 (maxDoubles is now 0).
  6. target is 2, which is even, but we're out of double moves. So now we have to simply subtract 1 to continue. The target becomes 1, and we increment ans by 1 (so ans is now 4).
  7. We have now reached 1, so we don't need to enter the loop again. There is no need to add the difference between target and 1 to ans, because target is already 1.
  8. The loop is finished, and the ans value is 4. This is the least number of moves needed to get from 1 to 10 with a maximum of 2 doubles.

In this particular case, the ans (which is 4) represents the smallest number of moves required to go from 1 to 10 when you can double no more than 2 times. With these moves, we've utilized both available doubles efficiently and only incremented when necessary.

Solution Implementation

1class Solution:
2    def min_moves(self, target: int, max_doubles: int) -> int:
3        # Initialize the number of moves to 0
4        moves = 0
5      
6        # Continue until no more doubles are allowed,
7        # or the target is reduced to 1
8        while max_doubles and target > 1:
9            # Increment the move count for every operation
10            moves += 1
11          
12            # If the target is odd, subtract 1 (increment operation)
13            if target % 2 == 1:
14                target -= 1
15            else:
16                # If the target is even, use a double operation
17                max_doubles -= 1   # Use one of the allowed doubles
18                target >>= 1       # Halve the target by right shifting
19      
20        # After using all doubles, add the remaining distance to 1 
21        # (all remaining moves are increments)
22        moves += target - 1
23      
24        # Return the total number of moves
25        return moves
26
27# The method name `min_moves` is used to initiate an action to find the minimum moves.
28# The variable `moves` is more readable and standardized according to Python naming conventions.
29# Comments are provided to explain what each segment of the code is doing.
30
1class Solution {
2    public int minMoves(int target, int maxDoubles) {
3        // This variable stores the number of moves required to reduce the target to 1.
4        int moves = 0;
5      
6        // Continue the loop until we have no more doubling operations available
7        // or until the target becomes 1.
8        while (maxDoubles > 0 && target > 1) {
9            // Increment the move count with each iteration of the loop.
10            moves++;
11          
12            // If the target is odd, we subtract one to make it even (operation type 1).
13            if (target % 2 == 1) {
14                target--;
15            } else {
16                // If the target is even and we still have doubling operations left,
17                // we use one and halve the target (operation type 2).
18                maxDoubles--;
19                target /= 2; // equivalent to target >>= 1, but clearer with respect to halving.
20            }
21        }
22      
23        // If there are no double operations left, add the remaining (target - 1)
24        // to the moves as we can only decrement by 1 in each move from then on.
25        moves += target - 1;
26      
27        // The total number of moves is returned.
28        return moves;
29    }
30}
31
1class Solution {
2public:
3    // Function to compute the minimum number of moves required to reach 'target' starting from 1.
4    // `maxDoubles` defines the maximum number of times the doubling operation can be performed.
5    int minMoves(int target, int maxDoubles) {
6        int numMoves = 0;  // Initialize a counter for the number of moves.
7      
8        // Continue reducing 'target' while doubles are still available and 'target' is greater than 1.
9        while (maxDoubles > 0 && target > 1) {
10            numMoves++;  // Increment the moves counter.
11
12            // If 'target' is odd, perform an increment operation to make it even.
13            if (target % 2 == 1) {
14                target--;  // Decrement 'target' to make it even, which counts as a move.
15            } else {
16                maxDoubles--;  // Use a double operation and decrement the remaining doubles.
17                target /= 2;   // Halve the target since it's even.
18            }
19        }
20
21        // After finishing all the available doubles or reaching `target` <= 1,
22        // perform (target - 1) increment operations to reach exactly 'target'.
23        numMoves += target - 1;
24
25        // Return the total number of moves calculated.
26        return numMoves;
27    }
28};
29
1function minMoves(target: number, maxDoubles: number): number {
2    let moves = 0; // Initialize the count of moves
3  
4    // As long as there are remaining doubles and target is greater than 1, keep iterating
5    while (maxDoubles > 0 && target > 1) {
6        moves++; // Increment the move counter
7      
8        if (target % 2 === 1) {
9            // If the target is odd, decrement it to make it even
10            target--;
11        } else {
12            // If the target is even, utilize a double and halve the target
13            maxDoubles--;
14            target /= 2;
15        }
16    }
17  
18    // Once no more doubles are allowed, increment the move count directly to reach 1
19    moves += target - 1;
20  
21    return moves; // Return the total number of moves required
22}
23
Not Sure What to Study? Take the 2-min Quiz：

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Time and Space Complexity

The time complexity of the given code is O(log(target)). This is because the while loop can run at most log2(target) times if maxDoubles is sufficiently large. Each operation inside the loop involves either a simple subtraction by 1 (in case target is odd) or a division by 2 using bitwise right shift (in case target is even). The final operation outside the loop is a single subtraction, which is done in constant time.

The space complexity of the code is O(1) since no additional space is used that scales with the input size. All operations are performed using a fixed amount of variables (ans, target, and maxDoubles).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫