# LeetCode 754: Reach a Number

## Problem Restatement

We start at position `0` on an infinite number line.

There is a destination at position `target`.

On move `1`, we must move exactly `1` step.

On move `2`, we must move exactly `2` steps.

On move `3`, we must move exactly `3` steps.

In general, on move `i`, we must move exactly `i` steps.

For every move, we can choose either direction:

```text
left or right
```

Return the minimum number of moves needed to reach exactly `target`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `target` |
| Output | The minimum number of moves needed to reach `target` |
| Movement | On move `i`, move exactly `i` steps |
| Direction | Each move can go left or right |

Example function shape:

```python
def reachNumber(target: int) -> int:
    ...
```

## Examples

Example 1:

```python
target = 2
```

Output:

```python
3
```

One way to reach `2` in three moves is:

```text
0 -> 1 -> -1 -> 2
```

The moves are:

| Move | Direction | Position |
|---:|---|---:|
| `1` | right `1` | `1` |
| `2` | left `2` | `-1` |
| `3` | right `3` | `2` |

So the answer is `3`.

Example 2:

```python
target = 3
```

Output:

```python
2
```

We can move right twice:

```text
0 -> 1 -> 3
```

The moves are:

| Move | Direction | Position |
|---:|---|---:|
| `1` | right `1` | `1` |
| `2` | right `2` | `3` |

So the answer is `2`.

## First Thought: Search All Paths

A direct idea is to explore all possible directions.

At move `1`, we can go left or right.

At move `2`, each of those choices branches again.

So after `m` moves, there are up to:

```text
2^m
```

possible direction sequences.

That is too large.

We need to use the structure of the moves instead of searching every path.

## Key Insight

The direction does not matter at first.

Suppose we always move right.

After `m` moves, our position is:

```text
1 + 2 + 3 + ... + m
```

This sum is:

```text
m * (m + 1) / 2
```

Call this sum `s`.

If `s == target`, then `m` moves are enough.

If `s > target`, we may be able to flip some moves from right to left.

Flipping a move of size `x` changes the final position by:

```text
2 * x
```

because that move was contributing `+x`, and after flipping it contributes `-x`.

So the final position changes by an even number.

Therefore, after reaching a sum `s`, we can reach `target` exactly if:

```text
s - target is even
```

If `s - target` is odd, no set of flipped moves can fix the difference yet.

So we keep adding the next move until:

1. `s >= target`
2. `(s - target)` is even

## Why We Use Absolute Value

The number line is symmetric.

Reaching `target = 5` takes the same number of moves as reaching `target = -5`.

Every right move can be replaced by a left move, and every left move can be replaced by a right move.

So we can solve only for:

```python
target = abs(target)
```

## Algorithm

1. Replace `target` with `abs(target)`.
2. Start with:
   1. `moves = 0`
   2. `position = 0`
3. Keep adding the next move while either:
   1. `position < target`
   2. `position - target` is odd
4. Return `moves`.

In code, the loop condition is:

```python
while position < target or (position - target) % 2 == 1:
```

Each iteration adds one more move:

```python
moves += 1
position += moves
```

## Walkthrough

Take:

```python
target = 2
```

First use absolute value:

```python
target = abs(2) = 2
```

Now keep moving right.

| Move | Sum | Difference `sum - target` | Even? |
|---:|---:|---:|---|
| `1` | `1` | `-1` | No, sum is too small |
| `2` | `3` | `1` | No |
| `3` | `6` | `4` | Yes |

At move `3`, the sum is `6`.

The difference is:

```text
6 - 2 = 4
```

Since `4` is even, we can flip moves whose total is:

```text
4 / 2 = 2
```

That means flip the move of size `2`.

Original all-right path:

```text
+1 +2 +3 = 6
```

Flip `+2` into `-2`:

```text
+1 -2 +3 = 2
```

So `3` moves are enough.

## Correctness

We solve for `abs(target)` because the movement rules are symmetric around `0`. Any path to a positive target can be mirrored to reach the corresponding negative target with the same number of moves.

After `m` moves, if all moves go right, the farthest positive position is:

```text
s = 1 + 2 + ... + m
```

Every other reachable position after `m` moves is formed by choosing some of these moves and flipping them from right to left.

If we flip moves with total length `x`, the final position becomes:

```text
s - 2x
```

Therefore, a target is reachable after `m` moves exactly when `s >= target` and `s - target` is even.

The algorithm increases `m` from `0` upward and stops at the first `m` satisfying these two conditions.

Since smaller values of `m` were checked and failed, the returned number of moves is minimal.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(sqrt(target))` | The cumulative sum grows quadratically in the number of moves |
| Space | `O(1)` | Only a few integer variables are used |

The sum after `m` moves is about `m^2 / 2`, so we need about `sqrt(target)` moves before crossing the target.

## Implementation

```python
class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)

        moves = 0
        position = 0

        while position < target or (position - target) % 2 == 1:
            moves += 1
            position += moves

        return moves
```

## Code Explanation

We first reduce the problem to the positive side:

```python
target = abs(target)
```

Then we keep track of how many moves we have taken:

```python
moves = 0
```

and the farthest position we can reach by moving right every time:

```python
position = 0
```

The loop continues while the current all-right sum cannot be adjusted to exactly reach `target`:

```python
while position < target or (position - target) % 2 == 1:
```

There are two bad cases.

First, if `position < target`, we have not gone far enough yet.

Second, if `position - target` is odd, then flipping moves cannot fix the difference, because every flip changes the position by an even amount.

Inside the loop, we add the next move:

```python
moves += 1
position += moves
```

When the loop stops, `position >= target` and `position - target` is even.

That means we can flip some moves to land exactly on `target`.

So we return:

```python
return moves
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.reachNumber(2) == 3
    assert s.reachNumber(3) == 2
    assert s.reachNumber(1) == 1
    assert s.reachNumber(4) == 3
    assert s.reachNumber(5) == 5
    assert s.reachNumber(-2) == 3
    assert s.reachNumber(-3) == 2

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `2` | Needs overshoot and parity correction |
| `3` | Reached directly by `1 + 2` |
| `1` | Single move |
| `4` | `1 + 2 + 3 = 6`, flip `1` |
| `5` | Needs more moves because parity does not match early |
| `-2` | Confirms symmetry |
| `-3` | Negative direct mirror case |