Skip to content

754. Reach a Number

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.

 

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

Solutions

Solution 1: Mathematical Analysis

Due to symmetry, each time we can choose to move left or right, so we can take the absolute value of \(\textit{target}\).

Define \(s\) as the current position, and use the variable \(k\) to record the number of moves. Initially, both \(s\) and \(k\) are \(0\).

We keep adding to \(s\) in a loop until \(s \ge \textit{target}\) and \((s - \textit{target}) \bmod 2 = 0\). At this point, the number of moves \(k\) is the answer, and we return it directly.

Why? Because if \(s \ge \textit{target}\) and \((s - \textit{target}) \bmod 2 = 0\), we only need to change the sign of the positive integer \(\frac{s - \textit{target}}{2}\) to negative, so that \(s\) equals \(\textit{target}\). Changing the sign of a positive integer essentially means changing the direction of the move, but the actual number of moves remains the same.

The time complexity is \(O(\sqrt{\left | \textit{target} \right | })\), and the space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)
        s = k = 0
        while 1:
            if s >= target and (s - target) % 2 == 0:
                return k
            k += 1
            s += k

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int reachNumber(int target) {
        target = Math.abs(target);
        int s = 0, k = 0;
        while (true) {
            if (s >= target && (s - target) % 2 == 0) {
                return k;
            }
            ++k;
            s += k;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int s = 0, k = 0;
        while (1) {
            if (s >= target && (s - target) % 2 == 0) return k;
            ++k;
            s += k;
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func reachNumber(target int) int {
    if target < 0 {
        target = -target
    }
    var s, k int
    for {
        if s >= target && (s-target)%2 == 0 {
            return k
        }
        k++
        s += k
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
/**
 * @param {number} target
 * @return {number}
 */
var reachNumber = function (target) {
    target = Math.abs(target);
    let [s, k] = [0, 0];
    while (1) {
        if (s >= target && (s - target) % 2 == 0) {
            return k;
        }
        ++k;
        s += k;
    }
};

Comments