754. Reach a Number
1. Description
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.
2. Example
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).
3. Constraints
- $-10^9$ <= target <= $10^9$
- target != 0
4. Solutions
Greedy
n = target
Time complexity: O($\sqrt{n}$)
Space complexity: O(1)
class Solution {
public:
int reachNumber(int target) {
int result = 0;
// the number line is symmetric, so positive or negative numbers are identical
// we only care about the steps we need rather than how to move, so we suppose the target is positive
int target = abs(target);
for (int i = 1, sum = 0; !(sum >= target && ((sum - target) & 1) == 0); ++i) {
// the best situation is we continuously move right to match the target
// but if we can't exactly match the target, we can pass it and move back
// if we pass the target by 8, then we can change the direction of 4 to left from right
// the surplus number must be even
// so the condition to end the moving is sum >= target and sum - target is even
// before that, we keep moving right
sum += i;
result = i;
}
return result;
}
};