2139. Minimum Moves to Reach Target Score LeetCode Solution

In this guide, you will get 2139. Minimum Moves to Reach Target Score LeetCode Solution with the best time and space complexity. The solution to Minimum Moves to Reach Target Score problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Minimum Moves to Reach Target Score solution in C++
  4. Minimum Moves to Reach Target Score solution in Java
  5. Minimum Moves to Reach Target Score solution in Python
  6. Additional Resources
2139. Minimum Moves to Reach Target Score LeetCode Solution image

Problem Statement of Minimum Moves to Reach Target Score

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

See also  1486. XOR Operation in an Array LeetCode Solution

Constraints:

1 <= target <= 109
0 <= maxDoubles <= 100

Complexity Analysis

  • Time Complexity: O(\texttt{maxDoubles})
  • Space Complexity: O(1)

2139. Minimum Moves to Reach Target Score LeetCode Solution in C++

class Solution {
 public:
  int minMoves(int target, int maxDoubles) {
    int steps = 0;

    while (target > 1 && maxDoubles) {
      if (target % 2 == 1) {
        --target;
      } else {
        target /= 2;
        --maxDoubles;
      }
      ++steps;
    }

    return steps + target - 1;
  }
};
/* code provided by PROGIEZ */

2139. Minimum Moves to Reach Target Score LeetCode Solution in Java

class Solution {
  public int minMoves(int target, int maxDoubles) {
    int steps = 0;

    while (target > 1 && maxDoubles > 0) {
      if (target % 2 == 1) {
        --target;
      } else {
        target /= 2;
        --maxDoubles;
      }
      ++steps;
    }

    return steps + target - 1;
  }
}
// code provided by PROGIEZ

2139. Minimum Moves to Reach Target Score LeetCode Solution in Python

class Solution:
  def minMoves(self, target: int, maxDoubles: int) -> int:
    steps = 0

    while target > 1 and maxDoubles:
      if target % 2 == 1:
        target -= 1
      else:
        target //= 2
        maxDoubles -= 1
      steps += 1

    return steps + target - 1
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: