Watch 10 video solutions for Reach a Number, a medium level problem involving Math, Binary Search. This walkthrough by Algorithms Made Easy has 13,425 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |