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

Example 1

1
2
3
4

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

Example 2

1
2
3
4

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

Example 3

1
2
3
4

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

Method 1 – Recursive Dynamic Programming (Top-Down) 1

Intuition

We can represent the target as a sum of powers of x, and recursively try to build the target using the least number of operators. At each step, we can either add or subtract the closest power of x, and use memoization to avoid recomputation.

Approach

  1. For a given target, find the largest power k such that x^k <= target.
  2. Try two options:
    • Use x^k as many times as possible, then solve for the remainder.
    • Use x^(k+1) once, then solve for x^(k+1) - target.
  3. Recursively compute the minimum operators for both options and take the minimum.
  4. Use memoization to cache results for each target.
  5. The cost for using x^k is k if k > 0 (since xx…*x needs k multiplications), otherwise 2 (for division).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    unordered_map<int, int> memo;
    int x;
    int leastOpsExpressTarget(int X, int target) {
        x = X;
        return dfs(target);
    }
    int dfs(int t) {
        if (t == 0) return 0;
        if (t < x) return min(2 * t - 1, 2 * (x - t));
        if (memo.count(t)) return memo[t];
        int k = 0, p = 1;
        while (p * x <= t) {
            p *= x;
            ++k;
        }
        int left = dfs(t - p) + k;
        int right = dfs(p * x - t) + k + 1;
        return memo[t] = min(left, right);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func leastOpsExpressTarget(x int, target int) int {
    memo := map[int]int{}
    var dfs func(int) int
    dfs = func(t int) int {
        if t == 0 {
            return 0
        }
        if t < x {
            return min(2*t-1, 2*(x-t))
        }
        if v, ok := memo[t]; ok {
            return v
        }
        k, p := 0, 1
        for p*x <= t {
            p *= x
            k++
        }
        left := dfs(t-p) + k
        right := dfs(p*x-t) + k + 1
        memo[t] = min(left, right)
        return memo[t]
    }
    return dfs(target)
}
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    Map<Integer, Integer> memo = new HashMap<>();
    int x;
    public int leastOpsExpressTarget(int X, int target) {
        x = X;
        return dfs(target);
    }
    int dfs(int t) {
        if (t == 0) return 0;
        if (t < x) return Math.min(2 * t - 1, 2 * (x - t));
        if (memo.containsKey(t)) return memo.get(t);
        int k = 0, p = 1;
        while (p * x <= t) {
            p *= x;
            k++;
        }
        int left = dfs(t - p) + k;
        int right = dfs(p * x - t) + k + 1;
        int ans = Math.min(left, right);
        memo.put(t, ans);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    val memo = mutableMapOf<Int, Int>()
    var x = 0
    fun leastOpsExpressTarget(X: Int, target: Int): Int {
        x = X
        return dfs(target)
    }
    fun dfs(t: Int): Int {
        if (t == 0) return 0
        if (t < x) return minOf(2 * t - 1, 2 * (x - t))
        memo[t]?.let { return it }
        var k = 0; var p = 1
        while (p * x <= t) {
            p *= x; k++
        }
        val left = dfs(t - p) + k
        val right = dfs(p * x - t) + k + 1
        val ans = minOf(left, right)
        memo[t] = ans
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def leastOpsExpressTarget(x: int, target: int) -> int:
    memo: dict[int, int] = {}
    def dfs(t: int) -> int:
        if t == 0:
            return 0
        if t < x:
            return min(2 * t - 1, 2 * (x - t))
        if t in memo:
            return memo[t]
        k, p = 0, 1
        while p * x <= t:
            p *= x
            k += 1
        left = dfs(t - p) + k
        right = dfs(p * x - t) + k + 1
        memo[t] = min(left, right)
        return memo[t]
    return dfs(target)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn least_ops_express_target(x: i32, target: i32) -> i32 {
        use std::collections::HashMap;
        fn dfs(x: i32, t: i32, memo: &mut HashMap<i32, i32>) -> i32 {
            if t == 0 { return 0; }
            if t < x { return (2 * t - 1).min(2 * (x - t)); }
            if let Some(&v) = memo.get(&t) { return v; }
            let mut k = 0; let mut p = 1;
            while p * x <= t {
                p *= x; k += 1;
            }
            let left = dfs(x, t - p, memo) + k;
            let right = dfs(x, p * x - t, memo) + k + 1;
            let ans = left.min(right);
            memo.insert(t, ans);
            ans
        }
        let mut memo = HashMap::new();
        dfs(x, target, &mut memo)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    leastOpsExpressTarget(x: number, target: number): number {
        const memo: Record<number, number> = {};
        const dfs = (t: number): number => {
            if (t === 0) return 0;
            if (t < x) return Math.min(2 * t - 1, 2 * (x - t));
            if (t in memo) return memo[t];
            let k = 0, p = 1;
            while (p * x <= t) {
                p *= x; k++;
            }
            const left = dfs(t - p) + k;
            const right = dfs(p * x - t) + k + 1;
            memo[t] = Math.min(left, right);
            return memo[t];
        };
        return dfs(target);
    }
}

Complexity

  • ⏰ Time complexity: O(log(target)), since each recursive call reduces the target by a power of x.
  • 🧺 Space complexity: O(log(target)), for memoization and recursion stack.

Method 2 -

Code

Complexity

  • Time: O(nnnxxxnnn)
  • Space: O(nnnxxx)