Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/964.html

964. Least Operators to Express Number

Level

Hard

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:

  1. The division operator (/) returns rational numbers.
  2. There are no parentheses placed anywhere.
  3. We use the usual order of operations: multiplication and division happens before addition and subtraction.
  4. It’s 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.

Note:

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

Solution

Obviously, division is only needed when a 1 is needed. This problem can be solved using dynamic programming. First represent target in base x representation, with an array nums created. Then consider whether each term in base x representation can be reversed. For each term, calculate the number of operators when it is not reversed and when it is reversed. If the latter has fewer operators, then the term should be reversed, and the higher term will be affected.

Create an array dp, where dp[i] represents the difference between the number of operators in forward representation and the number of operators in backward representation. The last term in dp is Integer.MAX_VALUE. For the i-th term where i starts from 0, let count = i if i > 0 or count = 2 if i == 0, and calculate forward = nums[i] * count and backward = (x - nums[i]) * count + Math.min(dp[i + 1] - i - 1, i + 1). Then add the minimium of forward and backward to the total number of operators, and set dp[i] = Math.max(0, backward - forward). Finally, return the total number of operators.

  • class Solution {
    public int leastOpsExpressTarget(int x, int target) {
        int[] nums = new int[32];
        int index = 0;
        while (target > 0) {
            nums[index] = target % x;
            target /= x;
            index++;
        }
        int lastBackward = Integer.MAX_VALUE;
        int opsCount = -1;
        for (int i = index - 1; i >= 0; i--) {
            int count = i == 0 ? 2 : i;
            int forward = nums[i] * count;
            int backward = (x - nums[i]) * count + Math.min(lastBackward - i - 1, i + 1);
            opsCount += Math.min(forward, backward);
            lastBackward = Math.max(0, backward - forward);
        }
        return opsCount;
    }
}

All Problems

All Solutions