<p>Given a single positive integer <code>x</code>, we will write an expression of the form <code>x (op1) x (op2) x (op3) x ...</code> where each operator <code>op1</code>, <code>op2</code>, etc. is either addition, subtraction, multiplication, or division (<code>+</code>, <code>-</code>, <code>*</code>, or <code>/)</code>. For example, with <code>x = 3</code>, we might write <code>3 * 3 / 3 + 3 - 3</code> which is a value of <font face="monospace">3</font>.</p>

<p>When writing such an expression, we adhere to the following conventions:</p>

<ul>
	<li>The division operator (<code>/</code>) returns rational numbers.</li>
	<li>There are no parentheses placed anywhere.</li>
	<li>We use the usual order of operations: multiplication and division happen before addition and subtraction.</li>
	<li>It is not allowed to use the unary negation operator (<code>-</code>). For example, &quot;<code>x - x</code>&quot; is a valid expression as it only uses subtraction, but &quot;<code>-x + x</code>&quot; is not because it uses negation.</li>
</ul>

<p>We would like to write an expression with the least number of operators such that the expression equals the given <code>target</code>. Return the least number of operators used.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> x = 3, target = 19
<strong>Output:</strong> 5
<strong>Explanation:</strong> 3 * 3 + 3 * 3 + 3 / 3.
The expression contains 5 operations.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> x = 5, target = 501
<strong>Output:</strong> 8
<strong>Explanation:</strong> 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5.
The expression contains 8 operations.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> x = 100, target = 100000000
<strong>Output:</strong> 3
<strong>Explanation:</strong> 100 * 100 * 100 * 100.
The expression contains 3 operations.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= x &lt;= 100</code></li>
	<li><code>1 &lt;= target &lt;= 2 * 10<sup>8</sup></code></li>
</ul>

class Solution {
public:
    vector<pair<long long int, long long int>> vp;

    void init(long long int x) {
        vp.clear();
        vp.push_back({1, 2});

        int i = 1;
        while (vp.back().first * x <= 100000000000000ll)
            vp.push_back({vp.back().first * x, i++});
    }
    int leastOpsExpressTarget(int x, int target) {
        init(x);

        unordered_map<long long int, long long int> dp[2];
        int cur = 0, prev = 1;

        long long int MAX_X = x;

        while (MAX_X / x <= target)
            MAX_X *= x;

        long long int ans = INT_MAX;

        dp[cur][target] = 0;

        long long int base_x = 0, base_x_plus_1 = 1;

        while (dp[cur].size() > 0) {
            swap(prev, cur);

            dp[cur].clear();

            for (auto [num, cost] : dp[prev]) {
                if (num == 0) {
                    ans = min(ans, cost);
                    continue;
                }

                long long int delta = num % vp[base_x_plus_1].first;

                if (abs(num - delta) < MAX_X)
                    dp[cur][num - delta] = min(
                        dp[cur].count(num - delta) ? dp[cur][num - delta]
                                                   : INT_MAX,
                        cost + delta / vp[base_x].first * vp[base_x].second);

                delta = vp[base_x_plus_1].first - delta;

                if (abs(num + delta) < MAX_X)
                    dp[cur][num + delta] = min(
                        dp[cur].count(num + delta) ? dp[cur][num + delta]
                                                   : INT_MAX,
                        cost + delta / vp[base_x].first * vp[base_x].second);
            }

            base_x++;
            base_x_plus_1++;
        }

        return ans - 1;
    }
};
9300