Skip to main content

754. Reach a Number

medium

Starting at 0 on a number line, on step n you move exactly n units left or right. What is the minimum number of steps to reach target? A clever parity-and-triangular-number observation collapses it to closed form.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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 i-th 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.

Constraints

  • -10^9 <= target <= 10^9
  • target != 0

Examples

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).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Symmetry: the answer is the same for target and -target. Replace target with |target|.

Hint 2

After n moves with sum 1 + 2 + ... + n = n*(n+1)/2 = T_n, the position is T_n minus 2k for some k (the sum of steps you chose to go left, doubled because flipping a +k step to -k changes position by 2k).

Hint 3

So target is reachable in n moves iff T_n >= target AND (T_n - target) is even (so we can split the excess into a flip).

Hint 4

Find the smallest n with T_n >= target. If (T_n - target) is even, return n. Otherwise increment n until T_n - target is even — happens within 1 or 2 more steps.

Solution approach

Reveal approach

Replace target with abs(target). Find the smallest n such that the triangular number T_n = n*(n+1)/2 >= target. Quick way: solve T_n >= target for n, get n ~= ceil((-1 + sqrt(1 + 8*target)) / 2), or just loop adding steps until the sum reaches target. Then check parity: if (T_n - target) is even, n moves suffice — flip the (T_n - target) / 2 -th positive step to negative. If (T_n - target) is odd, take one or two extra steps to get the right parity: incrementing n by 1 adds n+1 to the sum, flipping parity when n+1 is odd. So you may need n or n+1 or n+2. Loop until parity matches. O(sqrt(target)) time, O(1) space.

Complexity

Time
O(sqrt(n))
Space
O(1)

Related patterns

  • math
  • parity
  • triangular-numbers

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

Practice these live with InterviewChamp.AI

Drill Reach a Number and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →