754. Reach a Number

2023, Jan 15 2 mins read

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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
    }
};

Search

Tags