LeetCode 0754. Reach a Number Solution in Java, C++, Python & More | Explanation + Code

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 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 target and (s - 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 target and (s - target) \bmod 2 = 0, we only need to change the sign of the positive integer ^{s - target}⁄₂ to negative, so that s equals 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(√\left | target \right | ), and the space complexity is O(1).

PythonJavaC++GoJavaScript

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(code-box)

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; } } }(code-box)

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; } } };(code-box)

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 } }(code-box)

/** * @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; } };(code-box)