Skip to main content
Talentd

Reach a Number - Solution & Explanation

MediumMathBinary Search19 min readAsked at: Amazon, Microsoft, Meta +5
Practice this problem

Problem Statement

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 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 <= 109
  • target != 0

Approach Overview

Problem 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 1: Approach 1: Divide and Conquer

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 2: Approach 2: Dynamic Programming

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: Mathematical Analysis

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

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Divide and Conquer

Time Complexity: O(n log n)
Space Complexity: O(n)

Approach 2: Dynamic Programming

Time Complexity: O(n)
Space Complexity: O(n)

Mathematical Analysis—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Divide and Conquer / Binary Search on Step CountO(sqrt(n))O(1)Optimal solution. Uses triangular sum and parity insight to compute minimal moves efficiently.
Dynamic ProgrammingO(n * sqrt(n))O(n)Useful for understanding the reachable state space or building intuition before deriving the math optimization.

Video Solution

Reach a Number | Live Coding with Explanation | Leetcode #754 • Algorithms Made Easy • 13,684 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Reach a Number easy or hard?
Reach a Number is rated Medium because the brute-force idea is simple but the optimal insight is mathematical. Candidates who recognize the triangular number pattern and parity adjustment can solve it quickly, while others may struggle with exploring all left/right move combinations.
Reach a Number Python/Java solution
Python and Java implementations usually compute the minimal step count k such that k(k+1)/2 >= |target|. Then they adjust k until the difference between the triangular sum and target is even. The algorithm uses constant space and only a small loop to reach the correct step count.
How to solve Reach a Number in O(n)?
A straightforward simulation increments the step size and keeps adding moves until the cumulative sum reaches or exceeds the target. After that, check whether the difference between the sum and target is even; if not, continue adding steps until the parity condition holds. This linear stepping process effectively finds the minimal valid k.
What is the best approach for Reach a Number?
The optimal approach uses a mathematical observation about triangular numbers. Find the smallest k where the sum 1 + 2 + ... + k is at least |target|. If the difference between the sum and the target is even, you can flip directions of some moves to land exactly on the target. This runs in O(sqrt(n)) time and O(1) space.
Is Reach a Number asked at Google/Amazon/Meta?
Reach a Number is a common medium-level math puzzle used in technical interviews at companies like Google and Amazon. It tests whether candidates recognize patterns in cumulative sums and parity instead of attempting brute-force search across directions.
What data structure is used in Reach a Number?
The optimal solution does not rely on complex data structures. It primarily uses mathematical reasoning with integers and cumulative sums. Alternative explanations sometimes use dynamic programming to track reachable positions, but the interview-preferred method uses simple arithmetic.
What is the time complexity of Reach a Number?
The optimal solution runs in O(sqrt(n)) time because the triangular number k(k+1)/2 grows quadratically, so only about sqrt(target) steps are checked. Space complexity is O(1) since only a few variables are needed to track the cumulative sum and step count.

Ready to solve this problem?

Practice Reach a Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Ways to Reach a Position After Exactly k Steps