Solution


Approach 1: Dynamic Programming

Intuition

First, we notice that we can consider blocks of multiplication and division separately. Each block is a power of x: either x / x, x, x * x, x * x * x, x * x * x * x and so on. (There is no point to write expressions like x * x / x because it uses strictly more operators.)

Let's think of the cost of a block as all the operators needed to express it, including the addition or subtraction operator in front of it. For example, we can think of x * x + x + x / x as (+ x * x) (+ x) (+ x / x) for a cost of 2 + 1 + 2, minus 1 for the leading + (so the total cost is 4).

We can write the cost of writing a block that has value : it is , except when it is 2. We want the sum of the costs of all blocks minus 1.

Now, we have the reduced problem: we have the costs of writing all or , and we want to find the least cost to express the target.

Notice that modulo , the only blocks that change the expression are . Let . So we must either subtract 's, or add 's. This will form a new "remaining" target, , that is divisible by .

Then, modulo , the only blocks that change the expression are and . However, since the new target is divisible by , there is no point to use , as we would have to use at least of them to do the same work as one use of , which is a strictly higher cost.

Again, in a similar way, we have , and we must either subtract 's, or add 's. This will form a new remaining target , and so on.

As a concrete example, say x = 5, target = 123. We either add 2 or subtract 3. This leaves us with a target of 120 or 125. If the target is 120, we can either add 5 or subtract 20, leaving us with a target of 100 or 125. If the target is 100, we can either add 25 or subtract 100, leaving us with a target of 125 or 0. If the target is 125, we subtract 125.

Algorithm

Let's calculate dp(i, target) using a top down dp. Here, i will be the exponent of the block being considered, and target will be the remaining target, already divided by .

From here, the recursion is straightforward: , and we either subtract blocks or add of them. The base cases are easily deduced - see the code for more details.

Complexity Analysis

  • Time Complexity: . We can prove that we only visit up to two states for each base-x digit of .

  • Space Complexity: .


Analysis written by: @awice.