> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Least Operators to Express Number

> Tested Python solution for LeetCode 964 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 964, [Hard](/catalog/hard). Topics: [Math](/catalog/topics/math), [Dynamic Programming](/catalog/topics/dynamic-programming), [Memoization](/catalog/topics/memoization). [View on LeetCode](https://leetcode.com/problems/least-operators-to-express-number/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 964   # by problem number
lcpy gen -s least_operators_to_express_number   # by problem name
```

## Problem

Given a single positive integer `x`, we will write an expression of the form `x (op1) x (op2) x (op3) x ...` where each operator `op1`, `op2`, etc. is either addition, subtraction, multiplication, or division (`+`, `-`, `*`, or `/`). For example, with `x = 3`, we might write `3 * 3 / 3 + 3 - 3` which is a value of `3`.

When writing such an expression, we adhere to the following conventions:

* The division operator (`/`) returns rational numbers.
* There are no parentheses placed anywhere.
* We use the usual order of operations: multiplication and division happen before addition and subtraction.
* It is not allowed to use the unary negation operator (`-`). For example, `x - x` is a valid expression as it only uses subtraction, but `-x + x` is not because it uses negation.

We would like to write an expression with the least number of operators such that the expression equals the given `target`. Return the least number of operators used.

### Examples

```
Input: x = 3, target = 19
Output: 5
Explanation: 3 * 3 + 3 * 3 + 3 / 3.
The expression contains 5 operations.
```

```
Input: x = 5, target = 501
Output: 8
Explanation: 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5.
The expression contains 8 operations.
```

```
Input: x = 100, target = 100000000
Output: 3
Explanation: 100 * 100 * 100 * 100.
The expression contains 3 operations.
```

### Constraints

* `2 <= x <= 100`
* `1 <= target <= 2 * 10^8`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/least_operators_to_express_number/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/least_operators_to_express_number/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(log_x(target)^2 * x)
    # Space: O(log_x(target))
    def least_ops_express_target(self, x: int, target: int) -> int:
        # An expression is a signed sum of blocks, where a block is a power x^k
        # written as x * x * ... * x (k-1 inner operators, k >= 1) or x / x for 1
        # (1 inner operator). Each block after the first also costs its leading +/-.
        # Counting that leading operator in the block cost gives cost(k) = k for
        # k >= 1 and cost(0) = 2, and the answer is the minimum total cost minus 1.
        # Choosing a_i copies (negative for subtraction) of each x^i means
        # sum(a_i * x^i) == target, so a_i is fixed modulo x by the remainder:
        # walk the base-x digits keeping the cheapest carry per position.
        costs: dict[tuple[int, int], int] = {(0, target): 0}
        while costs:
            (exp, remaining), total = min(costs.items(), key=lambda item: item[1])
            del costs[(exp, remaining)]
            if remaining == 0:
                return total - 1
            digit = remaining % x
            block_cost = 2 if exp == 0 else exp
            for offset in range(-3, 4):
                # Carry up to 2 units into the next digit, in either direction.
                amount = digit + offset * x
                key = (exp + 1, (remaining - amount) // x)
                candidate = total + abs(amount) * block_cost
                if key not in costs or candidate < costs[key]:
                    costs[key] = candidate
        raise ValueError("unreachable")
```

## Complexity

| Time | Space |
| - | - |
| O(log\_x(target)^2 \* x) | O(log\_x(target)) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.