Least Operators to Express Number

hard dynamic programming math base-x

Problem

Given a single positive integer x, you build an expression that uses x repeatedly together with the operators +, −, × and ÷ (standard precedence, no parentheses, no unary minus). Each x written down costs one usage, and the operators between them are counted. Return the least number of operators needed to make the expression equal target.

The trick: x × x × … × x is a power of x and uses (power − 1) operators, while x ÷ x = 1 uses one operator. So every term costs a number of operators tied to which power of x it represents. Process target in base x, and at each digit decide whether to add that many copies of the current power or subtract from the next higher power.

Inputx = 3, target = 19

Output5

19 = 3×3 + 3×3 + 3 ÷ 3 → (×) + (+) + (×) + (+) + (÷) = 5 operators. Two copies of 9 plus one unit (3÷3), each operator counted once.

x (base, ≥ 2)

target

def least_ops_express_target(x, target):
    # pos = min ops to reach the current low part exactly
    # neg = min ops to overshoot it (so a higher power can subtract back down)
    # Per copy of x**k we pay weight: k==0 -> 2 (x / x), k >= 1 -> k.
    pos = neg = 0
    k = 0
    while target:
        cur = target % x                    # base-x digit at power k
        if k == 0:
            pos = cur * 2                    # cur units, each x / x costs 2
            neg = (x - cur) * 2              # overshoot by (x - cur) units, borrow 1 from x**1
        else:
            pos_cost = cur * k               # place cur copies of x**k
            neg_cost = (x - cur) * k         # place (x - cur) copies to overshoot
            new_pos = min(pos_cost + pos, pos_cost + k + neg)
            new_neg = min(neg_cost + pos, neg_cost - k + neg)
            pos, neg = new_pos, new_neg
        target //= x
        k += 1
    return min(pos, k + neg) - 1             # drop the leading '+' we over-counted

function leastOpsExpressTarget(x, target) {
  let pos = 0, neg = 0, k = 0;
  while (target) {
    const cur = target % x;
    if (k === 0) {
      pos = cur * 2;
      neg = (x - cur) * 2;
    } else {
      const posCost = cur * k;
      const negCost = (x - cur) * k;
      const newPos = Math.min(posCost + pos, posCost + k + neg);
      const newNeg = Math.min(negCost + pos, negCost - k + neg);
      pos = newPos; neg = newNeg;
    }
    target = Math.floor(target / x);
    k++;
  }
  return Math.min(pos, k + neg) - 1;
}

class Solution {
    public int leastOpsExpressTarget(int x, int target) {
        long pos = 0, neg = 0;
        int k = 0;
        while (target > 0) {
            int cur = target % x;
            if (k == 0) {
                pos = (long) cur * 2;
                neg = (long) (x - cur) * 2;
            } else {
                long posCost = (long) cur * k;
                long negCost = (long) (x - cur) * k;
                long newPos = Math.min(posCost + pos, posCost + k + neg);
                long newNeg = Math.min(negCost + pos, negCost - k + neg);
                pos = newPos; neg = newNeg;
            }
            target /= x;
            k++;
        }
        return (int) (Math.min(pos, k + neg) - 1);
    }
}

class Solution {
public:
    int leastOpsExpressTarget(int x, int target) {
        long long pos = 0, neg = 0;
        int k = 0;
        while (target > 0) {
            int cur = target % x;
            if (k == 0) {
                pos = (long long) cur * 2;
                neg = (long long) (x - cur) * 2;
            } else {
                long long posCost = (long long) cur * k;
                long long negCost = (long long) (x - cur) * k;
                long long newPos = min(posCost + pos, posCost + k + neg);
                long long newNeg = min(negCost + pos, negCost - k + neg);
                pos = newPos; neg = newNeg;
            }
            target /= x;
            k++;
        }
        return (int) (min(pos, (long long) k + neg) - 1);
    }
};

Explanation

We build target out of copies of x joined by + - × ÷, and want the fewest operators. The neat insight is that the cheap building blocks are powers of x: a power x**k costs k operators, and the single unit 1 = x ÷ x costs 2.

So we look at target in base x, one digit at a time. The digit at power k tells us how many copies of x**k we'd add. But sometimes it is cheaper to overshoot and subtract back down using a higher power, so at each step we track two costs: pos (build it exactly) and neg (overshoot it).

Moving to the next digit, pos can come from the previous exact build, and neg can borrow a higher power and subtract. We take the cheaper option each time with the min(...) updates.

At the end we compare finishing exactly (pos) versus borrowing one more power and subtracting (k + neg), and subtract 1 to remove the phantom leading + we counted.

Example: x = 3, target = 19 gives 19 = 9 + 9 + 1 as 3×3 + 3×3 + 3÷3, which uses 5 operators.

Time: O(log_x target) Space: O(1)