Problem

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 _theminimum number of moves required (i.e., the minimum _numMoves ) to reach the destination.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5

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 <= 10^9
  • target != 0

Solution

Intuition

At each move, you can go left or right, and the step size increases by 1 each time. The sum of the first k natural numbers is k*(k+1)/2. We want to find the smallest k such that we can reach target (possibly by flipping the direction of some moves). The key is: if the sum overshoots the target, and the difference is even, we can flip some moves to reach exactly target.

Approach

  1. Take the absolute value of target (problem is symmetric).
  2. Incrementally add steps (1, 2, 3, …) until the sum >= target and (sum - target) is even.
  3. The answer is the number of steps taken.

Code

C++

1
2
3
4
5
6
7
8
9

int reachNumber(int target) {
    target = abs(target);
    int sum = 0, k = 0;
    while (sum < target || (sum - target) % 2 != 0) {
        ++k;
        sum += k;
    }
    return k;
}

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func reachNumber(target int) int {
    if target < 0 {
        target = -target
    }
    sum, k := 0, 0
    for sum < target || (sum-target)%2 != 0 {
        k++
        sum += k
    }
    return k
}

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int reachNumber(int target) {
        target = Math.abs(target);
        int sum = 0, k = 0;
        while (sum < target || (sum - target) % 2 != 0) {
            ++k;
            sum += k;
        }
        return k;
    }
}

Kotlin

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

fun reachNumber(target: Int): Int {
    var t = Math.abs(target)
    var sum = 0
    var k = 0
    while (sum < t || (sum - t) % 2 != 0) {
        k++
        sum += k
    }
    return k
}

Python

1
2
3
4
5
6
7

def reachNumber(target):
    target = abs(target)
    sum_, k = 0, 0
    while sum_ < target or (sum_ - target) % 2 != 0:
        k += 1
        sum_ += k
    return k

Rust

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn reach_number(target: i32) -> i32 {
        let mut t = target.abs();
        let mut sum = 0;
        let mut k = 0;
        while sum < t || (sum - t) % 2 != 0 {
            k += 1;
            sum += k;
        }
        k
    }
}

TypeScript

1
2
3
4
5
6
7
8
9

function reachNumber(target: number): number {
    target = Math.abs(target);
    let sum = 0, k = 0;
    while (sum < target || (sum - target) % 2 !== 0) {
        k++;
        sum += k;
    }
    return k;
}

Complexity

  • ⏰ Time complexity: O(sqrt(target)) — The number of steps grows roughly as sqrt(target).
  • 🧺 Space complexity: O(1) — Only a few variables are used.