LeetCode 964: Least Operators to Express Number

Problem Restatement

We are given two integers:

x
target

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

+
-
*
/

Division is real division, and standard operator precedence applies.

We cannot use unary negation. So:

-x

is not allowed directly.

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

Return that minimum number.

The official constraints are:

Source: LeetCode problem statement. (leetcode.com)

Input and Output

Example function shape:

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

Examples

Example 1:

x = 3
target = 19

Output:

5

One optimal expression is:

3 * 3 + 3 * 3 + 3 / 3

This equals:

9 + 9 + 1 = 19

Operator count:

*
+
*
+
/

Total:

5

Example 2:

x = 5
target = 501

Output:

8

Example 3:

x = 100
target = 100000000

Output:

3

Expression:

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:

x = 3
target = 19

Base 3 representation:

19 = 2 * 9 + 0 * 3 + 1

That means:

19 = 2 * (3^2) + 1

The powers of x are important:

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

Each power has a cost.

To build:

x^k

we need:

k

multiplication operators.

But there is one special case:

1 = x / x

which costs one division operator.

So:

Recursive Choice

Suppose:

target = q * x + r

where:

0 <= r < x

We have two choices.

Choice 1: Build Upward

Use:

r copies

of the lower power.

Example:

target = 19
x = 3

19 = 6 * 3 + 1

We recursively build:

6

then add one more unit.

Choice 2: Overshoot Then Subtract

Instead of using r, use:

x - r

and subtract from the next higher multiple.

Example:

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:

dfs(t)

as the minimum operator cost to build t.

We recursively divide by x:

q, r = divmod(t, x)

Then compare:

build q and add r copies

versus:

build q + 1 and subtract x - r copies

Memoization avoids recomputing states.

Base Cases

If:

t == 0

then no operators are needed.

If:

t < x

then there are two ways to build t.

Add Small Units

Build:

t * (x / x)

Cost:

2 * t - 1

because each 1 costs division, and additions connect them.

Subtract From x

Build:

x - (x - t)

Cost:

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:

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:

1 + 1 + ...

versus:

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.

Implementation

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:

@cache

so repeated subproblems are computed only once.

If:

t == 0

then no expression is needed:

return 0

For small targets:

if t < x:

we compare two constructions.

Build directly with ones:

2 * t - 1

Example:

2 = x/x + x/x

This uses:

/
+

which is 3 operators.

Or subtract from x:

x - (x/x + ...)

with cost:

2 * (x - t)

For larger targets:

q, r = divmod(t, x)

We recursively solve the quotient.

Positive construction:

use_positive = dfs(q) + r

Negative construction:

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

Then we add operator costs for connecting pieces:

if q > 0:
    use_positive += 1

and:

if r > 0:
    use_negative += 1

Finally:

return min(use_positive, use_negative)

chooses the cheaper construction.

Testing

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: