964. Least Operators to Express Number

Description

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 * 10⁸

Solutions

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)\).

The execution logic of function \(dfs(v)\) is as follows:

If \(x \geq v\), then we can obtain \(v\) by adding \(v\) instances of \(x / x\), with the number of operators being \(v \times 2 - 1\); or we can obtain \(v\) by subtracting \((x - v)\) instances of \(x / x\) from \(x\), with the number of operators being \((x - v) \times 2\). We take the minimum of the two.

Otherwise, we enumerate \(x^k\) starting from \(k=2\) to find the first \(k\) where \(x^k \geq v\):

If \(x^k - v \geq v\) at this point, then we can only first obtain \(x^{k-1}\), then recursively calculate \(dfs(v - x^{k-1})\). The number of operators in this case is \(k - 1 + dfs(v - x^{k-1})\);
If \(x^k - v < v\) at this point, then we can obtain \(v\) in the above manner, with the number of operators being \(k - 1 + dfs(v - x^{k-1})\); or we can first obtain \(x^k\), then recursively calculate \(dfs(x^k - v)\), with the number of operators being \(k + dfs(x^k - v)\). We take the minimum of the two.

To avoid redundant calculations, we implement the \(dfs\) function using memoization search.

The time complexity is \(O(\log_{x}{target})\) and the space complexity is \(O(\log_{x}{target})\).

Python3JavaC++GoTypeScript

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)

class Solution {
    private int x;
    private Map<Integer, Integer> f = new HashMap<>();

    public int leastOpsExpressTarget(int x, int target) {
        this.x = x;
        return dfs(target);
    }

    private int dfs(int v) {
        if (x >= v) {
            return Math.min(v * 2 - 1, 2 * (x - v));
        }
        if (f.containsKey(v)) {
            return f.get(v);
        }
        int k = 2;
        long y = (long) x * x;
        while (y < v) {
            y *= x;
            ++k;
        }
        int ans = k - 1 + dfs(v - (int) (y / x));
        if (y - v < v) {
            ans = Math.min(ans, k + dfs((int) y - v));
        }
        f.put(v, ans);
        return ans;
    }
}

class Solution {
public:
    int leastOpsExpressTarget(int x, int target) {
        unordered_map<int, int> f;
        function<int(int)> dfs = [&](int v) -> int {
            if (x >= v) {
                return min(v * 2 - 1, 2 * (x - v));
            }
            if (f.count(v)) {
                return f[v];
            }
            int k = 2;
            long long y = x * x;
            while (y < v) {
                y *= x;
                ++k;
            }
            int ans = k - 1 + dfs(v - y / x);
            if (y - v < v) {
                ans = min(ans, k + dfs(y - v));
            }
            f[v] = ans;
            return ans;
        };
        return dfs(target);
    }
};

func leastOpsExpressTarget(x int, target int) int {
    f := map[int]int{}
    var dfs func(int) int
    dfs = func(v int) int {
        if x > v {
            return min(v*2-1, 2*(x-v))
        }
        if val, ok := f[v]; ok {
            return val
        }
        k := 2
        y := x * x
        for y < v {
            y *= x
            k++
        }
        ans := k - 1 + dfs(v-y/x)
        if y-v < v {
            ans = min(ans, k+dfs(y-v))
        }
        f[v] = ans
        return ans
    }
    return dfs(target)
}

function leastOpsExpressTarget(x: number, target: number): number {
    const f: Map<number, number> = new Map();
    const dfs = (v: number): number => {
        if (x > v) {
            return Math.min(v * 2 - 1, 2 * (x - v));
        }
        if (f.has(v)) {
            return f.get(v)!;
        }
        let k = 2;
        let y = x * x;
        while (y < v) {
            y *= x;
            ++k;
        }
        let ans = k - 1 + dfs(v - Math.floor(y / x));
        if (y - v < v) {
            ans = Math.min(ans, k + dfs(y - v));
        }
        f.set(v, ans);
        return ans;
    };
    return dfs(target);
}

964. Least Operators to Express Number

Description

Solutions

Solution 1: Memoization Search

Comments