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:
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 <= 109target != 0Problem Overview: You start at position 0 on an infinite number line. On the kth move you can go either left or right by exactly k steps. The goal is to reach a given target using the minimum number of moves.
Approach 1: Divide and Conquer / Binary Search on Steps (O(sqrt(n)) time, O(1) space)
The key observation comes from math. If you take k moves, the maximum distance you can reach in one direction is the triangular sum 1 + 2 + ... + k = k(k+1)/2. Instead of simulating every path, compute the smallest k such that this sum is at least |target|. If the difference sum - target is even, you can flip the direction of some moves to correct the overshoot. If it is odd, increase k until the parity becomes even. You can find the minimal valid k by iteratively increasing steps or applying binary search over possible move counts. The divide-and-conquer thinking comes from reducing the problem to finding the smallest step count that satisfies both the distance and parity constraints.
Approach 2: Dynamic Programming (O(n * sqrt(n)) time, O(n) space)
A dynamic programming approach models reachable positions after each move. Define a DP state representing positions reachable after k moves. For each step, you transition from previous positions by adding or subtracting k. This effectively explores the state space layer by layer until the target appears. Because the reachable range grows roughly proportional to the triangular number sequence, the number of states expands quickly, making this solution less practical for large targets. However, it demonstrates the brute-force search space clearly and helps reason about why parity and cumulative sums determine reachability.
Recommended for interviews: The mathematical step-sum solution is what interviewers expect. It reduces the problem to analyzing triangular numbers and parity instead of exploring all paths. Starting with a DP or brute-force explanation shows understanding of the state space, but recognizing the k(k+1)/2 distance property and parity adjustment demonstrates stronger algorithmic insight.
This approach involves breaking down the problem into smaller subproblems, solving each subproblem recursively, and then combining the results. This is a classic Divide and Conquer approach which can be applied to a variety of problems, such as sorting algorithms (e.g., Merge Sort).
This C code implements the Merge Sort algorithm using the Divide and Conquer strategy. The array is divided into two halves, each is sorted recursively, and then the two halves are merged together. The merge function combines two sorted subarrays into a single sorted array.
Time Complexity: O(n log n)
Space Complexity: O(n)
Dynamic Programming (DP) is an approach that solves complex problems by breaking them down into simpler subproblems and storing the results to avoid recomputing. It's particularly useful for optimization problems where decisions depend on previous decisions.
This C code demonstrates a dynamic programming solution for computing Fibonacci numbers. It uses memoization to store previously calculated results in the dp array, avoiding redundant calculations.
Time Complexity: O(n)
Space Complexity: O(n)
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 \frac{s - target}{2} 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(\sqrt{\left | target \right | }), and the space complexity is O(1).
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Divide and Conquer | Time Complexity: O(n log n) |
| Approach 2: Dynamic Programming | Time Complexity: O(n) |
| Mathematical Analysis | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer / Binary Search on Step Count | O(sqrt(n)) | O(1) | Optimal solution. Uses triangular sum and parity insight to compute minimal moves efficiently. |
| Dynamic Programming | O(n * sqrt(n)) | O(n) | Useful for understanding the reachable state space or building intuition before deriving the math optimization. |
Reach a Number | Live Coding with Explanation | Leetcode #754 • Algorithms Made Easy • 13,425 views views
Watch 9 more video solutions →Practice Reach a Number with our built-in code editor and test cases.
Practice on FleetCode