In this guide, you will get 754. Reach a Number LeetCode Solution with the best time and space complexity. The solution to Reach a Number 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.
You are standing at position 0 on an infinite number line. There is a destination at position target.
You can make some number of moves numMoves so that:
On each move, you can either go left or right.
During the ith move (starting from i == 1 to i == numMoves), you take i steps in the chosen direction.
Given the integer target, return the minimum number of moves required (i.e., the minimum numMoves) to reach the destination.
Example 1:
Input: target = 2
Output: 3
Explanation:
On the 1st move, we step from 0 to 1 (1 step).
On the 2nd move, we step from 1 to -1 (2 steps).
On the 3rd move, we step from -1 to 2 (3 steps).
Example 2:
Input: target = 3
Output: 2
Explanation:
On the 1st move, we step from 0 to 1 (1 step).
On the 2nd move, we step from 1 to 3 (2 steps).
Constraints:
-109 <= target <= 109
target != 0
Complexity Analysis
Time Complexity: O(\sqrt{\texttt{target}})
Space Complexity: O(1)
754. Reach a Number LeetCode Solution in C++
class Solution {
public:
int reachNumber(int target) {
const int newTarget = abs(target);
int ans = 0;
int pos = 0;
while (pos < newTarget)
pos += ++ans;
while ((pos - newTarget) % 2 == 1)
pos += ++ans;
return ans;
}
}; /* code provided by PROGIEZ */
754. Reach a Number LeetCode Solution in Java
class Solution {
public int reachNumber(int target) {
final int newTarget = Math.abs(target);
int ans = 0;
int pos = 0;
while (pos < newTarget)
pos += ++ans;
while ((pos - newTarget) % 2 == 1)
pos += ++ans;
return ans;
}
} // code provided by PROGIEZ
754. Reach a Number LeetCode Solution in Python
class Solution:
def reachNumber(self, target: int) -> int:
ans = 0
pos = 0
target = abs(target)
while pos < target:
ans += 1
pos += ans
while (pos - target) % 2 == 1:
ans += 1
pos += ans
return ans # code by PROGIEZ
