{x}
blog image

Least Operators to Express Number

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.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

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

Solution Explanation

This problem asks for the minimum number of operations (+, -, *, /) needed to express a target number using a given base number x. We can solve this efficiently using dynamic programming with memoization. The core idea is to recursively explore possible combinations of operations, always aiming to minimize the operator count.

Recursive Approach with Memoization:

The solution employs a recursive function dfs(v) that takes the current value v as input. The base cases are:

  1. x >= v: If the current value v is less than or equal to x, we can obtain it with at most two operations. We calculate min(v * 2 - 1, 2 * (x - v)). This considers reaching v either by repeatedly adding x (up to v times), or by repeatedly subtracting x.

  2. Memoization: If the result for v is already computed (f.containsKey(v) in Java, f[v] in Python), it is directly returned. This prevents redundant computations and significantly improves performance.

The recursive step involves finding the optimal number of operations to reach v from x. It determines the smallest power of x that is greater than or equal to v (k). Then, it explores two possibilities:

  1. Subtract: We consider reaching v by subtracting x^(k-1) from x^k and recursively call dfs(v - x^(k-1)). This approach adds k - 1 operations to reach x^(k-1) plus the operations required to reach v from x^(k-1).

  2. Add: If x^k - v < v, it means reaching v by adding x^(k-1) to reach x^k - v and recursively calculating dfs(x^k - v) is potentially more efficient. This path involves k operations to reach x^k and the operations to reach v from x^k.

The minimum of these two possibilities is selected as the optimal solution.

Time Complexity Analysis:

The time complexity is difficult to express precisely as a simple function. In the worst case, the recursion tree can explore a large number of possibilities. However, memoization drastically reduces the number of repeated computations. Without memoization, the complexity would be exponential. With memoization, the complexity becomes approximately O(target), as each distinct value of v is visited at most once during the recursive calls. In the average case it will be less than O(target) because the number of recursive calls is limited by the memoization.

Space Complexity Analysis:

The space complexity is dominated by the memoization table f. In the worst case, the size of the table can be proportional to the target value. Therefore, the space complexity is O(target).

Code Examples:

The provided code implements the recursive solution with memoization in several programming languages (Python, Java, C++, Go, TypeScript). All versions follow the same algorithmic approach. The memoization techniques differ slightly based on the language's features (e.g., @cache decorator in Python, HashMap in Java, etc.) but their purpose is the same.