# LeetCode 964: Least Operators to Express Number

## Problem Restatement

We are given two integers:

```python
x
target
```

We may build expressions using only the number `x` and the operators:

```python
+
-
*
/
```

Division is real division, and standard operator precedence applies.

We cannot use unary negation. So:

```python
-x
```

is not allowed directly.

We want to express `target` using the minimum number of operators.

Return that minimum number.

The official constraints are:

| Constraint | Value |
|---|---|
| `2 <= x <= 100` | Base number |
| `1 <= target <= 2 * 10^8` | Desired value |

Source: LeetCode problem statement. ([leetcode.com](https://leetcode.com/problems/least-operators-to-express-number/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `x` |
| Input | Integer `target` |
| Output | Minimum number of operators needed |
| Allowed numbers | Only repeated uses of `x` |

Example function shape:

```python
def leastOpsExpressTarget(x: int, target: int) -> int:
    ...
```

## Examples

Example 1:

```python
x = 3
target = 19
```

Output:

```python
5
```

One optimal expression is:

```python
3 * 3 + 3 * 3 + 3 / 3
```

This equals:

```python
9 + 9 + 1 = 19
```

Operator count:

```python
*
+
*
+
/
```

Total:

```python
5
```

Example 2:

```python
x = 5
target = 501
```

Output:

```python
8
```

Example 3:

```python
x = 100
target = 100000000
```

Output:

```python
3
```

Expression:

```python
100 * 100 * 100 * 100
```

This uses three multiplication operators.

## First Thought: Build Expressions Directly

We could try generating expressions recursively.

At each step:

- multiply by `x`
- divide by `x`
- add another term
- subtract another term

But the number of expressions grows explosively.

We need a mathematical structure.

## Key Insight

The expression behaves like writing the target in base `x`.

Example:

```python
x = 3
target = 19
```

Base `3` representation:

```python
19 = 2 * 9 + 0 * 3 + 1
```

That means:

```python
19 = 2 * (3^2) + 1
```

The powers of `x` are important:

```python
x^0 = 1
x^1 = x
x^2 = x * x
x^3 = x * x * x
```

Each power has a cost.

To build:

```python
x^k
```

we need:

```python
k
```

multiplication operators.

But there is one special case:

```python
1 = x / x
```

which costs one division operator.

So:

| Value | Cost |
|---|---|
| `x^0 = 1` | `2` operands but `1` operator |
| `x^k` | `k` operators |

## Recursive Choice

Suppose:

```python
target = q * x + r
```

where:

```python
0 <= r < x
```

We have two choices.

### Choice 1: Build Upward

Use:

```python
r copies
```

of the lower power.

Example:

```python
target = 19
x = 3

19 = 6 * 3 + 1
```

We recursively build:

```python
6
```

then add one more unit.

### Choice 2: Overshoot Then Subtract

Instead of using `r`, use:

```python
x - r
```

and subtract from the next higher multiple.

Example:

```python
19 = 7 * 3 - 2
```

Sometimes subtracting fewer pieces is cheaper than adding many pieces.

So we take the minimum of the two strategies.

## Dynamic Programming Interpretation

Define:

```python
dfs(t)
```

as the minimum operator cost to build `t`.

We recursively divide by `x`:

```python
q, r = divmod(t, x)
```

Then compare:

```python
build q and add r copies
```

versus:

```python
build q + 1 and subtract x - r copies
```

Memoization avoids recomputing states.

## Base Cases

If:

```python
t == 0
```

then no operators are needed.

If:

```python
t < x
```

then there are two ways to build `t`.

### Add Small Units

Build:

```python
t * (x / x)
```

Cost:

```python
2 * t - 1
```

because each `1` costs division, and additions connect them.

### Subtract From x

Build:

```python
x - (x - t)
```

Cost:

```python
2 * (x - t)
```

We choose the cheaper one.

## Correctness

We prove that the recursive relation computes the minimum number of operators.

Every valid expression ultimately builds the target using powers of `x`. Dividing the target by `x` gives:

```python
target = q * x + r
```

where `0 <= r < x`.

Any expression for `target` must resolve this remainder in one of two ways.

The first possibility is to construct `q * x` and then add `r`.

The second possibility is to construct `(q + 1) * x` and subtract `(x - r)`.

These are the only two nearest multiples of `x`, so every optimal expression must follow one of these two strategies.

The recursive calls compute the optimal cost for the quotient part. The remainder adjustment cost is added according to how many low-power terms are needed.

For targets smaller than `x`, the algorithm directly compares the only two meaningful constructions:

```python
1 + 1 + ...
```

versus:

```python
x - ...
```

and chooses the smaller operator count.

Memoization guarantees that each subproblem is solved optimally once and reused consistently.

Therefore, the recursion explores all optimal constructions and returns the minimum operator count.

## Complexity

The recursion repeatedly divides the target by `x`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(log_x(target))` | Each recursive step reduces the target size |
| Space | `O(log_x(target))` | Memoization and recursion depth |

## Implementation

```python
from functools import cache

class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        @cache
        def dfs(t: int) -> int:
            if t == 0:
                return 0

            if t < x:
                return min(
                    2 * t - 1,
                    2 * (x - t),
                )

            q, r = divmod(t, x)

            use_positive = dfs(q) + r
            use_negative = dfs(q + 1) + (x - r)

            if q > 0:
                use_positive += 1

            if r > 0:
                use_negative += 1

            return min(use_positive, use_negative)

        return dfs(target)
```

## Code Explanation

We memoize recursive results:

```python
@cache
```

so repeated subproblems are computed only once.

If:

```python
t == 0
```

then no expression is needed:

```python
return 0
```

For small targets:

```python
if t < x:
```

we compare two constructions.

Build directly with ones:

```python
2 * t - 1
```

Example:

```python
2 = x/x + x/x
```

This uses:

```python
/
+
```

which is `3` operators.

Or subtract from `x`:

```python
x - (x/x + ...)
```

with cost:

```python
2 * (x - t)
```

For larger targets:

```python
q, r = divmod(t, x)
```

We recursively solve the quotient.

Positive construction:

```python
use_positive = dfs(q) + r
```

Negative construction:

```python
use_negative = dfs(q + 1) + (x - r)
```

Then we add operator costs for connecting pieces:

```python
if q > 0:
    use_positive += 1
```

and:

```python
if r > 0:
    use_negative += 1
```

Finally:

```python
return min(use_positive, use_negative)
```

chooses the cheaper construction.

## Testing

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

    assert s.leastOpsExpressTarget(3, 19) == 5
    assert s.leastOpsExpressTarget(5, 501) == 8
    assert s.leastOpsExpressTarget(100, 100000000) == 3

    assert s.leastOpsExpressTarget(3, 1) == 1
    assert s.leastOpsExpressTarget(3, 2) == 2
    assert s.leastOpsExpressTarget(2, 7) == 4
    assert s.leastOpsExpressTarget(2, 1) == 1
    assert s.leastOpsExpressTarget(10, 10) == 0

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `(3, 19)` | Official-style mixed construction |
| `(5, 501)` | Larger recursive decomposition |
| `(100, 100000000)` | Pure multiplication chain |
| `(3, 1)` | Smallest nonzero target |
| `(3, 2)` | Small target below `x` |
| `(2, 7)` | Binary-style recursive behavior |
| `(2, 1)` | Single division construction |
| `(10, 10)` | Exact match with no operators needed |