# Reach a Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reach-a-number)
Canonical: https://scaleengineer.com/dsa/problems/reach-a-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Companies:** [Commvault](https://scaleengineer.com/companies/commvault), [InMobi](https://scaleengineer.com/companies/inmobi)
---
## 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 `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
## Brute-Force using Breadth-First Search (BFS)
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.
**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.
**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.
### Explanation
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.

```java
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
    }
}
```
### 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.

## Iterative Mathematical Approach
This approach moves away from brute-force and uses a mathematical insight. The problem is symmetric, so reaching `target` or `-target` takes the same number of moves. We can therefore assume `target` is positive. The core idea is to find the smallest number of moves, `k`, such that the sum of steps `S = 1 + 2 + ... + k` is not only greater than or equal to `target`, but also `S - target` is an even number. This even difference ensures that we can change the sign of some moves (which changes the sum by an even amount) to land exactly on `target`.
**Time:** O(sqrt(target)). The first loop runs until `k*(k+1)/2 >= target`, which means `k` is proportional to `sqrt(target)`. The second loop runs at most twice. · **Space:** O(1), as we only use a few variables to store the state (`k`, `sum`).
**Pros:** Very efficient compared to the brute-force approach.; Simple and intuitive to implement.; Constant space complexity.
**Cons:** Involves a loop that depends on the magnitude of `target`, making it slightly less performant than a pure O(1) formulaic solution.
### Explanation
We start by making `target` positive. Then, we iteratively find the smallest `k` such that the sum of steps from 1 to `k` (`sum`) is at least `target`. This gives us a potential number of moves. We then check the difference `delta = sum - target`. If `delta` is even, we can always find a combination of moves to flip (from `+` to `-`) to reduce the sum by exactly `delta`, so `k` is our answer. If `delta` is odd, we can't reach the target with `k` moves. We must take more moves. We increment `k` and update `sum` until `sum - target` becomes even. This process is guaranteed to terminate quickly (in at most two additional steps) because adding `k+1` and then `k+2` will change the parity of the difference correctly.

```java
class Solution {
    public int reachNumber(int target) {
        target = Math.abs(target);
        int k = 0;
        long sum = 0;
        while (sum < target) {
            k++;
            sum += k;
        }
        
        while ((sum - target) % 2 != 0) {
            k++;
            sum += k;
        }
        
        return k;
    }
}
```
### Algorithm
- First, handle the symmetry of the problem by taking the absolute value of the target: `target = Math.abs(target)`.
- Initialize the number of moves `k = 0` and the cumulative sum of steps `sum = 0`.
- Find the smallest `k` such that the sum of all positive steps `sum = 1 + 2 + ... + k` is greater than or equal to `target`. This is done with a loop:
  - `while (sum < target)`:
    - `k++`
    - `sum += k`
- At this point, `sum >= target`. Calculate the difference `delta = sum - target`.
- The key insight is that `delta` must be an even number. This is because flipping any move `i` from `+i` to `-i` changes the total sum by `-2i`, which is an even number. Therefore, to reduce `sum` to `target`, the difference must be a multiple of 2.
- If `delta` is not even, we must take more steps. We continue incrementing `k` and adding it to `sum` until `(sum - target)` is even.
  - `while ((sum - target) % 2 != 0)`:
    - `k++`
    - `sum += k`
- The final value of `k` is the minimum number of moves required. This second loop will execute at most twice.

## O(1) Mathematical Approach with Formula
This is the most optimal solution, which refines the iterative mathematical approach by replacing the initial loop with a direct analytical formula. It calculates the minimum `k` such that the sum of steps `1 + ... + k` surpasses the target in constant time. After finding this initial `k`, it uses the same parity-based logic to determine if `k`, `k+1`, or `k+2` is the correct answer, resulting in an overall constant time solution.
**Time:** O(1), as it involves a fixed number of arithmetic operations, including `sqrt`, which is considered constant time for practical purposes. · **Space:** O(1), as it only uses a fixed number of variables for calculation.
**Pros:** Extremely efficient, providing a solution in constant time.; Optimal in terms of both time and space complexity.
**Cons:** The mathematical formula might be less intuitive to derive than the iterative solution.; Requires careful handling of floating-point arithmetic and conversion to integers.
### Explanation
The foundation of this approach is identical to the previous one: find the smallest `k` such that `sum = k*(k+1)/2 >= target` and `sum - target` is even. Instead of looping to find `k`, we solve the inequality `k^2 + k - 2*target >= 0` directly. The positive root is `(-1 + sqrt(1 + 8*target))/2`. The smallest integer `k` is the ceiling of this value. Once `k` is found, we calculate `sum` and `delta = sum - target`. If `delta` is even, `k` is the answer. If `delta` is odd, we know we need more steps. A simple analysis of parity shows that if `k` is even, `k+1` moves will suffice. If `k` is odd, `k+2` moves are required. This allows us to find the answer with a few calculations, completely avoiding loops.

```java
class Solution {
    public int reachNumber(int target) {
        target = Math.abs(target);
        
        // We need k such that k*(k+1)/2 >= target
        // k^2 + k - 2*target >= 0
        // Using quadratic formula, the positive root is (-1 + sqrt(1 + 8*target))/2
        // Our k is the ceiling of this value.
        long k = (long) Math.ceil((-1.0 + Math.sqrt(1.0 + 8.0 * target)) / 2.0);
        
        long sum = k * (k + 1) / 2;
        long delta = sum - target;
        
        if (delta % 2 == 0) {
            return (int) k;
        } else {
            // If delta is odd, we need more steps.
            // If k is even, k+1 is odd. sum becomes sum+k+1. delta becomes delta+k+1 (odd+odd=even). So k+1 steps.
            // If k is odd, k+1 is even. delta becomes delta+k+1 (odd+even=odd). We need one more step.
            // The next step k+2 is odd. delta becomes delta+k+1+k+2 (odd+even+odd=even). So k+2 steps.
            if (k % 2 == 0) { // k+1 is odd
                return (int) (k + 1);
            } else { // k is odd
                return (int) (k + 2);
            }
        }
    }
}
```
### Algorithm
- Take the absolute value of the target: `target = Math.abs(target)`.
- Directly calculate the smallest integer `k` that satisfies `k*(k+1)/2 >= target`. This can be found by solving the quadratic equation `k^2 + k - 2*target = 0` for `k` and taking the ceiling of the positive root. The formula is `k = ceil((-1 + sqrt(1 + 8*target)) / 2)`.
- Calculate the sum for this `k`: `sum = k*(k+1)/2`.
- Find the difference: `delta = sum - target`.
- If `delta` is even (`delta % 2 == 0`), then `k` is the minimum number of moves. Return `k`.
- If `delta` is odd, we need more moves. We check the parity of `k`:
  - If `k` is even, the next move `k+1` is odd. The new difference `delta + (k+1)` will be `odd + odd = even`. So, the answer is `k+1`.
  - If `k` is odd, the next move `k+1` is even. The new difference `delta + (k+1)` will be `odd + even = odd`. We need one more move. The subsequent move `k+2` is odd. The total difference `delta + (k+1) + (k+2)` will be `odd + even + odd = even`. So, the answer is `k+2`.

# Solutions
### Java

```java
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;
    }
  }
}

```

### JavaScript

```javascript
/** * @param {number} target * @return {number} */ var reachNumber = function ( target ) { target = Math . abs ( target ); let [ s , k ] = [ 0 , 0 ]; while ( 1 ) { if ( s >= target && ( s - target ) % 2 == 0 ) { return k ; } ++ k ; s += k ; } };
```

### CPP

```cpp
class Solution {
public:
  int reachNumber(int target) {
    target = abs(target);
    int s = 0, k = 0;
    while (1) {
      if (s >= target && (s - target) % 2 == 0)
        return k;
      ++k;
      s += k;
    }
  }
};

```

### Python

```python
class Solution:
    def reachNumber(self, target: int) -> int: target = abs(target) s = k = 0 while 1: if s >= target and (s - target) % 2 == 0: return k k += 1 s += k

```