Approach 1: Dynamic Programming
First, we notice that we can consider blocks of multiplication and division separately. Each block is a power of
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
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
125. If the target is
120, we can either add
5 or subtract
20, leaving us with a target of
125. If the target is
100, we can either add
25 or subtract
100, leaving us with a target of
0. If the target is
125, we subtract
dp(i, target) using a top down
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.
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.