Scale Engineer

Reach a Number

Med
#0708Time: O(2^k), where k is the minimum number of moves. We explore an exponentially growing number of states.Space: O(2^k), where k is the minimum number of moves. The queue can hold up to O(2^k) distinct positions at level k.2 companies
Patterns
Math
Algorithms
Binary Search
Companies
CommvaultInMobi

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach models the problem as a state-space search. A state is defined by the current position on the number line. We start at position 0 and perform a Breadth-First Search (BFS) to explore all possible positions reachable with an increasing number of moves. Each level in the BFS corresponds to one additional move. The first time we land on the target position, we have found the minimum number of moves required, as BFS naturally explores the search space layer by layer.

Algorithm

  • Initialize a queue q with the starting position 0.
  • Initialize moves = 0.
  • Start a loop that continues as long as the queue is not empty.
  • Inside the loop, increment moves to represent the current move number.
  • Process all nodes at the current level of the BFS. Get the queue size levelSize before starting the inner loop.
  • For each of the levelSize elements in the queue:
    • Dequeue the currentPos.
    • Calculate the two possible next positions: pos1 = currentPos + moves and pos2 = currentPos - moves.
    • If either pos1 or pos2 equals the target, we have found the minimum number of moves, so return moves.
    • To avoid redundant exploration in the next level, add pos1 and pos2 to a Set for the next level's positions.
  • After processing all nodes at the current level, add all unique positions from the Set into the main queue q.
  • This process guarantees finding the shortest path in terms of the number of moves.

Walkthrough

We use a queue to manage the positions to visit, starting with 0. We iterate level by level, where each level k corresponds to making the k-th move. For every position p reached after k-1 moves, we explore the two new positions p+k and p-k. If either of these is the target, we've found our answer, k. To manage the exponentially growing number of states, we can use a Set to store the unique positions for the next level, preventing duplicate states in the queue for the same level. However, due to the enormous state space (2^k states at level k), this approach is not feasible for the given constraints where target can be large, leading to a large number of required moves.

import java.util.HashSet;import java.util.LinkedList;import java.util.Queue;import java.util.Set; class Solution {    public int reachNumber(int target) {        // This approach is too slow and will cause TLE/MLE.        // It is for demonstration of a brute-force method.        Queue<Long> queue = new LinkedList<>();        queue.add(0L);        int moves = 0;         while (!queue.isEmpty()) {            moves++;            int levelSize = queue.size();            Set<Long> nextLevelPositions = new HashSet<>();            for (int i = 0; i < levelSize; i++) {                long currentPos = queue.poll();                                long pos1 = currentPos + moves;                if (pos1 == target) {                    return moves;                }                nextLevelPositions.add(pos1);                 long pos2 = currentPos - moves;                if (pos2 == target) {                    return moves;                }                nextLevelPositions.add(pos2);            }            // This check is to prune the search space, but it's still too large.            if (nextLevelPositions.size() > 50000) {                 // Heuristic to stop TLE in platforms, but the approach is flawed.                // A proper solution would not need this.                break;            }            queue.addAll(nextLevelPositions);        }        return -1; // Should not be reached with a correct algorithm    }}

Complexity

Time

O(2^k), where k is the minimum number of moves. We explore an exponentially growing number of states.

Space

O(2^k), where k is the minimum number of moves. The queue can hold up to O(2^k) distinct positions at level k.

Trade-offs

Pros

  • Conceptually simple and easy to understand.

  • Guaranteed to find the minimum number of moves if it could run to completion.

Cons

  • Extremely inefficient in terms of both time and memory.

  • The number of possible positions to check grows exponentially with the number of moves (2^k).

  • Will result in Time Limit Exceeded (TLE) and Memory Limit Exceeded (MLE) for the given constraints.

Solutions

class Solution {public  int reachNumber(int target) {    target = Math.abs(target);    int s = 0, k = 0;    while (true) {      if (s >= target && (s - target) % 2 == 0) {        return k;      }      ++k;      s += k;    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem