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 basex digit of .

Space Complexity: .
Analysis written by: @awice.