#964

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Least Operators to Express Number

Compute the minimum number of arithmetic operators to form a target using repeated x with addition, subtraction, multiplication, or division in dynamic programming.

math dynamic programming memoization

Problem Statement

Given a positive integer x, construct an expression using multiple copies of x combined with addition (+), subtraction (-), multiplication (*), or division (/). The goal is to generate a valid expression that evaluates exactly to a given target value while minimizing the number of operators used.

Each expression must follow conventional arithmetic rules, and operators can be used in any order with repeated x values. Return the minimum number of operators required to represent the target using x in such a formula.

Examples

Example 1

Input: x = 3, target = 19

Output: 5

3 * 3 + 3 * 3 + 3 / 3. The expression contains 5 operations.

Example 2

Input: x = 5, target = 501

Output: 8

5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5. The expression contains 8 operations.

Example 3

Input: x = 100, target = 100000000

Output: 3

100 * 100 * 100 * 100. The expression contains 3 operations.

Constraints

2 <= x <= 100
1 <= target <= 2 * 108

Solution Approach

Recursive State with Memoization

Define a recursive function that considers every way to split the target into smaller components expressed by powers of x. Cache results in a memoization table to prevent recalculating operator counts for the same sub-targets.

Handling Base Cases and Powers

Treat small targets directly as multiples of x. For larger targets, explore expressions using x raised to different powers combined with addition or subtraction. Accurately counting the operators at each step ensures the minimum total is found.

Combining Subproblems Efficiently

For each division of the target, recursively compute the operator count for the quotient and remainder. Aggregate these counts and choose the combination with the fewest operators, exploiting state transition DP to track optimal solutions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on the range of powers of x considered and the memoization of sub-targets. Recursive state transitions reduce redundant calculations, but worst-case depth relates to log_x(target).

What Interviewers Usually Probe

Ask how to minimize operators when combining powers of x.
Probe understanding of memoization in recursive state transitions.
Check if candidates handle both quotient and remainder optimally.

Common Pitfalls or Variants

Common pitfalls

Failing to account for both addition and subtraction when splitting target.
Recomputing operator counts without memoization, causing timeouts.
Incorrectly counting operators for powers of x or ignoring division edge cases.

Follow-up variants

Restrict expressions to only addition and multiplication and find minimal operators.
Allow negative x and explore impact on operator minimization.
Find expressions minimizing total operands instead of operators.

FAQ

What is the best strategy for Least Operators to Express Number?

Use state transition dynamic programming with memoization to track minimal operator counts for each sub-target.

How do I handle very large targets efficiently?

Break the target into powers of x and use memoization to avoid recalculating intermediate operator counts.

Are divisions always counted as one operator?

Yes, each arithmetic operation, including division, counts as a single operator when forming the expression.

Can this approach handle any x between 2 and 100?

Yes, the recursive DP with memoization scales efficiently for all x in the given constraints.

Why is memoization crucial in this problem?

Memoization prevents redundant recursive calculations, ensuring that large targets and multiple sub-targets are processed efficiently.

terminal

Solution

Solution 1: Memoization Search

We define a function $dfs(v)$, which represents the minimum number of operators needed to compose the number $v$ using $x$. Then the answer is $dfs(target)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        @cache
        def dfs(v: int) -> int:
            if x >= v:
                return min(v * 2 - 1, 2 * (x - v))
            k = 2
            while x**k < v:
                k += 1
            if x**k - v < v:
                return min(k + dfs(x**k - v), k - 1 + dfs(v - x ** (k - 1)))
            return k - 1 + dfs(v - x ** (k - 1))

        return dfs(target)

Continue Practicing

#913 cat and mouse #1137 n th tribonacci number #509 fibonacci number