Reach a Number

medium math binary search

Problem

Starting at 0 on a number line, on the i-th move you take exactly i steps left or right. Return the minimum number of moves required to reach the integer target.

Inputtarget=2

Output3

Moves are -1, +2, +1 totalling 2 in 3 steps with even overshoot parity.

input

def reachNumber(target):
    target = abs(target)
    k = 0; total = 0
    while total < target or (total - target) % 2:
        k += 1
        total += k
    return k

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

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

class Solution {
public:
  int reachNumber(int target) {
    target = abs(target);
    int k = 0; long total = 0;
    while (total < target || (total - target) % 2 != 0) {
      k++;
      total += k;
    }
    return k;
  }
};

Explanation

On move i you step exactly i spaces left or right. First, by symmetry, reaching target or -target takes the same number of moves, so we work with |target|.

If you take k moves all to the right, you land at total = 1 + 2 + ... + k. The key idea: flipping any one move from right to left changes the landing spot by an even amount (you lose i and gain -i, a swing of 2i). So with k moves you can reach any value with the same parity as total, as long as total ≥ target.

So we grow k step by step, adding k to total, and stop at the first k where total ≥ target and the overshoot total - target is even. That overshoot can be split evenly between the flips, landing us exactly on target.

Example: target = 2. With k=1, total=1 (too small). k=2, total=3, overshoot 1 (odd, no). k=3, total=6, overshoot 4 (even, yes). Answer is 3 — e.g. moves -1, +2, +1.

Because total grows like k(k+1)/2, the answer is near √target, so the loop is short.

Time: O(sqrt(target)) Space: O(1)