LeetCode 964 - Least Operators to Express Number

This problem asks us to construct a mathematical expression using only the number x repeatedly, combined with the operators +, -, , and /, such that the final expression evaluates exactly to target.

leetcodehardmathdynamic-programmingmemoization

LeetCode Problem 964

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming, Memoization

Solution

Problem Understanding

This problem asks us to construct a mathematical expression using only the number x repeatedly, combined with the operators +, -, *, and /, such that the final expression evaluates exactly to target.

The challenge is not simply reaching the target value, but doing so with the minimum number of operators.

For example, if x = 3 and target = 19, one optimal expression is:

3 * 3 + 3 * 3 + 3 / 3

This evaluates to:

9 + 9 + 1 = 19

and uses 5 operators:

*, +, *, +, /

Several constraints make this problem significantly harder than it first appears.

First, we cannot use parentheses, so normal operator precedence rules apply automatically. Multiplication and division happen before addition and subtraction.

Second, unary negation is forbidden. We cannot write -x, although expressions like x - x are valid.

Third, division produces rational numbers, which is extremely important. Since:

x / x = 1

we can always construct the number 1 using exactly one operator.

The input consists of:

  • x, the only number we are allowed to use
  • target, the value we must express

The output is the minimum number of operators needed.

The constraints are:

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

The target can be very large, which immediately tells us that brute force expression generation is infeasible. We need a highly optimized mathematical strategy.

Several edge cases are important:

  • When target < x, multiplication is not useful immediately, and we must build the value using additions or subtractions involving 1 = x/x.
  • When target is exactly a power of x, the optimal answer is straightforward multiplication.
  • Sometimes it is cheaper to overshoot and subtract rather than build the value directly. For example, representing 24 with x = 5 is cheaper as 25 - 1 than constructing 24 directly.
  • Because subtraction is allowed, multiple representations must be considered at every step.

Approaches

Brute Force Approach

A brute force solution would attempt to generate all valid expressions using repeated copies of x and different operator combinations, then evaluate which expressions equal target.

Conceptually, this works because every valid expression can eventually be enumerated. We could recursively try:

  • adding another x
  • subtracting another x
  • multiplying by another x
  • dividing by another x

and keep exploring until we reach the target.

However, this quickly becomes computationally impossible.

The number of possible expressions grows exponentially with expression length. Additionally, because division creates rational values, the state space becomes enormous. Even with pruning, the search tree explodes for targets near 2 * 10^8.

This approach is therefore completely impractical.

Key Insight

The crucial observation is that every number can be represented in base x.

For example:

target = 19, x = 3

19 = 2 * 3^2 + 0 * 3^1 + 1 * 3^0

This suggests we should think of the problem as constructing powers of x.

The cost of creating powers is predictable:

x^0 = x / x    -> cost 1
x^1 = x        -> cost 0
x^2 = x * x    -> cost 1
x^3 = x * x * x -> cost 2

In general:

cost(x^k) = k

operators.

Now the problem becomes a dynamic programming problem over the base-x digits of the target.

At each digit, we have two choices:

  • Build the digit directly
  • Overshoot to the next power and subtract

This creates a recursive optimization problem with overlapping subproblems, making memoization ideal.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Enumerates possible expressions recursively
Optimal O(log target) O(log target) Uses base-x decomposition with memoized DP

Algorithm Walkthrough

Step 1: Define the Cost of Building Powers

We first observe the operator cost for each power of x.

For example:

x^1 = x

requires no operator.

x^2 = x * x

requires one multiplication.

x^k

requires k - 1 multiplications, but in the DP formulation we treat the positional cost as k.

The special case is:

1 = x / x

which costs one operator.

Step 2: Convert the Problem Into Base-x

We repeatedly divide the target by x.

For example:

target = 19
x = 3

Base-3 representation:

19 = 2 * 9 + 0 * 3 + 1

The digits are processed from least significant to most significant.

Step 3: Maintain Two DP States

For every digit position k, we maintain:

  • positive, the minimum cost if we build the current remainder directly
  • negative, the minimum cost if we overshoot and later subtract

This is the central optimization trick.

Sometimes constructing:

digit * x^k

directly is expensive.

It may instead be cheaper to build:

(digit + 1) * x^k

and subtract the excess later.

Step 4: Transition Between States

Suppose:

target % x = remainder

At digit position k:

Direct construction cost:

remainder * k

Overshoot cost:

(x - remainder) * k

We update both DP states using the best possible transition.

Step 5: Continue Until the Entire Target Is Processed

We repeatedly divide the target by x:

target //= x

until the target becomes zero.

Each iteration processes one base-x digit.

Step 6: Return the Final Minimum

The final answer is:

min(positive, k + negative) - 1

The subtraction by 1 occurs because the first number does not require a leading operator.

Why it works

The algorithm works because every integer has a unique base-x representation. At every digit position, the optimal solution must either:

  • build the digit directly, or
  • overshoot and compensate later

The DP explores both possibilities while memoizing optimal costs. Since all valid constructions reduce to combinations of powers of x, and every power has a deterministic operator cost, the algorithm exhaustively considers all optimal representations without redundant computation.

Python Solution

class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        positive = 0
        negative = 0
        power_cost = 0

        while target:
            target, remainder = divmod(target, x)

            if power_cost == 0:
                positive = remainder * 2
                negative = (x - remainder) * 2
            else:
                next_positive = min(
                    remainder * power_cost + positive,
                    (remainder + 1) * power_cost + negative
                )

                next_negative = min(
                    (x - remainder) * power_cost + positive,
                    (x - remainder - 1) * power_cost + negative
                )

                positive = next_positive
                negative = next_negative

            power_cost += 1

        return min(positive, negative + power_cost) - 1

The implementation processes the target digit by digit in base x.

The variables positive and negative track the minimum operator counts for the two DP states. positive represents building the current prefix directly, while negative represents overshooting and subtracting later.

The variable power_cost corresponds to the current power of x. At position k, constructing one copy of x^k costs k operators.

The first digit is handled specially because representing 1 requires:

x / x

which costs two symbols and one operator in the DP accounting scheme.

For every subsequent digit, we compute two transitions:

  • direct construction
  • overshoot construction

Finally, we subtract one because the very first operand does not need a preceding operator.

Go Solution

func leastOpsExpressTarget(x int, target int) int {
    positive := 0
    negative := 0
    powerCost := 0

    for target > 0 {
        remainder := target % x
        target /= x

        if powerCost == 0 {
            positive = remainder * 2
            negative = (x - remainder) * 2
        } else {
            nextPositive := min(
                remainder*powerCost+positive,
                (remainder+1)*powerCost+negative,
            )

            nextNegative := min(
                (x-remainder)*powerCost+positive,
                (x-remainder-1)*powerCost+negative,
            )

            positive = nextPositive
            negative = nextNegative
        }

        powerCost++
    }

    return min(positive, negative+powerCost) - 1
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

The Go implementation follows the exact same DP logic as the Python version.

Because Go does not provide a built-in min function for integers, we define a helper manually.

All values safely fit within Go's int range under the given constraints, so no special overflow handling is required.

Unlike Python, Go requires explicit variable declarations and manual integer division handling, but otherwise the implementation structure is identical.

Worked Examples

Example 1

Input:

x = 3
target = 19

Base-3 representation:

19 = 2 * 3^2 + 0 * 3^1 + 1 * 3^0
Step Target Remainder Power Cost Positive Negative
Initial 19 - 0 0 0
1 6 1 0 2 4
2 2 0 1 2 3
3 0 2 2 6 5

Final answer:

min(6, 5 + 3) - 1
= min(6, 8) - 1
= 5

Optimal expression:

3 * 3 + 3 * 3 + 3 / 3

Example 2

Input:

x = 5
target = 501

Base-5 representation:

501 = 4 * 125 + 0 * 25 + 0 * 5 + 1
Step Target Remainder Power Cost Positive Negative
Initial 501 - 0 0 0
1 100 1 0 2 8
2 20 0 1 2 7
3 4 0 2 2 6
4 0 4 3 8 5

Final answer:

min(8, 5 + 4) - 1
= 8

Optimal expression:

5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5

Example 3

Input:

x = 100
target = 100000000

Since:

100000000 = 100^4

Expression:

100 * 100 * 100 * 100

Operator count:

3

Complexity Analysis

Measure Complexity Explanation
Time O(log target) One iteration per base-x digit
Space O(log target) Implicit recursion-equivalent DP state

The algorithm processes the target by repeatedly dividing by x, which means the number of iterations equals the number of digits in the base-x representation of the target.

Since:

digits = O(log_x(target))

the runtime is logarithmic.

Only a constant number of DP variables are maintained during iteration, so the actual auxiliary storage is constant. Some analyses describe the conceptual DP depth as logarithmic because the process mirrors recursive digit decomposition.

Test Cases

sol = Solution()

assert sol.leastOpsExpressTarget(3, 19) == 5  # provided example
assert sol.leastOpsExpressTarget(5, 501) == 8  # provided example
assert sol.leastOpsExpressTarget(100, 100000000) == 3  # exact power

assert sol.leastOpsExpressTarget(3, 1) == 1  # x/x
assert sol.leastOpsExpressTarget(3, 3) == 0  # just x
assert sol.leastOpsExpressTarget(3, 9) == 1  # x*x
assert sol.leastOpsExpressTarget(3, 27) == 2  # x*x*x

assert sol.leastOpsExpressTarget(5, 4) == 3  # build below x
assert sol.leastOpsExpressTarget(5, 6) == 2  # 5 + 5/5
assert sol.leastOpsExpressTarget(5, 24) == 4  # overshoot with 25 - 1

assert sol.leastOpsExpressTarget(2, 125) > 0  # small base, large target
assert sol.leastOpsExpressTarget(100, 1) == 1  # 100/100

assert sol.leastOpsExpressTarget(2, 1) == 1  # smallest possible target
assert sol.leastOpsExpressTarget(2, 2) == 0  # exact x
Test Why
(3, 19) Standard mixed-expression example
(5, 501) Demonstrates subtraction optimization
(100, 100000000) Exact power of x
(3, 1) Smallest constructible value
(3, 3) No operator required
(3, 9) Single multiplication
(3, 27) Multiple chained multiplications
(5, 4) Target smaller than x
(5, 6) Requires constructing 1
(5, 24) Overshoot and subtract strategy
(2, 125) Stress case with many digits
(100, 1) Large x, minimal target
(2, 1) Absolute lower boundary
(2, 2) Exact base value

Edge Cases

One important edge case occurs when target < x. In this scenario, multiplication is not immediately useful because even a single multiplication produces a value larger than the target. The algorithm must decide whether it is cheaper to build the target directly using repeated 1s or to overshoot using x and subtract back down. This is exactly why the positive and negative DP states both exist.

Another tricky case occurs when the target is exactly a power of x, such as:

x = 100
target = 100000000

A naive implementation might still explore unnecessary addition and subtraction combinations. The DP formulation naturally handles this efficiently because the base-x representation contains a single nonzero digit.

A third subtle edge case involves representations that are cheaper when overshooting. For example:

24 with x = 5

Direct construction is expensive, but:

25 - 1

is much cheaper. Algorithms that only consider direct digit construction will fail here. The negative carry state ensures overshoot solutions are always considered.

Another potential source of bugs is handling the cost of constructing 1. Since:

1 = x / x

the operator count differs from higher powers of x. The implementation handles this by treating the lowest digit position separately when power_cost == 0.

Finally, the problem statement forbids unary negation. Expressions like -x + x are invalid. The DP never constructs standalone negative terms. Instead, subtraction is always represented as subtracting one valid expression from another, which fully complies with the problem constraints.