0754. Reach a Number¶

You are standing at position 0 on an infinite number line. There is a goal at position target.

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:

Input: target = 3
Output: 2
Explanation:
On the first move we step from 0 to 1.
On the second step we step from 1 to 3.

Example 2:

Input: target = 2
Output: 3
Explanation:
On the first move we step from 0 to 1.
On the second move we step  from 1 to -1.
On the third move we step from -1 to 2.

Note:

target will be a non-zero integer in the range [-10^9, 10^9].

Analysis¶

It's a math problem, and we can use the Pythagorean theorem to calculate the minimal steps to reach or be greater than the target number, and then by flipping one or more of the steps, we can finally reach the perfect number. There are two cases when our first minimal steps exceed the target, and we represent the difference as diff:

diff is an odd number: in this case, we just need to keep proceeding (step ++), because by flipping any number from 1 to step, it will result in a 2 * step number, which is guaranteed to be an even number.
diff is even: great, we can just flip a step within 1 to step, since we can guarantee diff is always less than the latest step, we can be sure that there exists a flip step so that 2 * flip step = diff.
Time: $O(1)$ by using math
Space: $O(1)$

Why can it guarantee to be the optimal solution? leetcode url

Code¶

Without using math:

class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int step = 0, sum = 0;
        for (; sum < target; sum += step)
            step ++;
        while ((sum - target) % 2 != 0) {
            sum += ++step;
        }
        return step;

    }
};

Using Pythagorean theorem:

class Solution {
public:
    int reachNumber(int64_t target) {
        target = std::abs(target);
        int64_t steps = 0.5*(sqrt(8*target)-1)+1, sum{(steps+1)*steps/2}, diff{sum - target};
        if(diff % 2 == 0) return steps;
        else if(steps % 2 == 0) return steps + 1;
        return steps + 2;
    }
};