Given $x$, $y$, $k$, convert $x$ to $y$ by multiplication by $k$ or subtraction of $1$ in the fewest steps

Question

Problem Statement:

We are given three positive integers $x$, $y$, and $k$, and our aim is to convert $x$ to $y$ in the minimum number of steps using one of the following two operations at each step:

• Multiply $x$ by $k$
• Subtract $1$ from $x$

Let convert($x$,$y$,$k$) be the minimum number of steps to convert $x$ to $y$ using $k$. Then find the values for the following:

1. convert(3,10,2)
2. convert(4,92,3)
3. convert(11,104250,2)
   

Note: Following are the official answers for the three parts mentioned above:

1. 3
2. 7
3. 24

My Approach: I think it is easier to go the other way round, i.e., to convert $y$ to $x$ using the opposite operations, which is to divide by $k$ or add $1$ at each step. I think this is easier because it restricts the possible cases as division is possible only when the number is a multiple of k. And while doing this we can avoid repeated calculations in case we encounter the same number some time later. For example, for convert(3,10,2), we have this,

I even coded a Breadth First Search solution for this problem (thought it is not so useful as the question was asked in a pen and paper based exam):

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = 1e16;

int main() {    
    const int lim = 10000;
    int t;
    cin >> t;
    while(t--) {
        ll x, y, k;
        cin >> x >> y >> k;
        map<ll,bool> vis;
        map<ll,int> dist;
        queue<ll> q;
        q.push(y);
        vis[y] = true;
        bool found = false;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            if(u == x) {
                found = true;
                break;
            }
            if(dist[u] < lim) {
                if(u+1<INF && !vis[u+1]) {
                    vis[u+1] = true;
                    dist[u+1] = 1+dist[u];
                    q.push(u+1);
                }
                if(u%k == 0 && !vis[u/k]) {
                    vis[u/k] = true;
                    dist[u/k] = 1+dist[u];
                    q.push(u/k);
                }
            }
        }
        if(found) cout << dist[x] << "\n";
        else cout << "-1\n";
    }
                
    return 0;
}

So my question is:

Can we do something better than to look through each possibility? Any observations that can help? I am looking for an answer that can help compute the values without the help of a computer.

Answer 1

(Fill in the gaps as needed. You should have everything that you need listed out here.)

Observations:

1. Each valid sequence of steps can be written as $ k (k (k ( \ldots ( x - a_n) - a_{n-1} ) - \ldots - a_1) - a_0= y $. This takes $ n + \sum_{i=0}^n a_i$ steps. This is a bijection.
2. Rewrite this as $k^n x - y = \sum a_i k^n$.
3. In particular, if $ k^n x - y < 0$, then there is no solution using multiplication by $k$ exactly $n$ times. (This should be obvious from the start).
4. For a fixed $N$ and $n$, the minimal $\sum_{i=0}^n a_i$ such that $ N=\sum_{i=0}^n a_i k^n$ happens when $ a_i < k$ for $ i < n$. There is a unique representation corresponding to the base $k$ representation of $N$. Note that $a_n$ is as large as it needs to be.
5. Hence, given a fixed $n, x, y, k$, the calculation for the minimum is straight forward.
6. We just need to test a several values of $n$, starting with $ \lceil \log_k \frac{y}{x} \rceil $, until $n >$ the minimum number of steps we're calculated so far. Note that the minimum doesn't always occur for the minimum $n$.

For example, in the first case,

• $ 3 \times 2^1 - 10 < 0$, so no solution here.
• $ 3 \times 2^2 - 10 = 2 = ( 1 \times 2^1) $ will take $ 2 + 1 = 3 $ steps.
• $ 3 \times 2^3 - 10 = 14 = ( 1 \times 2^3 + 1\times 2^2 + 1 \times 2 )$ will take $ 3 + 3 = 6 $ steps.
• We stop here since any larger $n$ is greater than the minimal steps calculated at this point.

And for the last case,

• Start with $\lceil \log_2 104250 / 11 \rceil = 14$.
• $11 \times 2^{14} - 104250 = 75974 = 410100011000110_2$, which takes $ 14 + 10 = 24$ steps.
• $ 11 \times 2^{15} - 104250 = 256198 = 7110100011000110_2$, which takes $ 15 + 14 = 29$ steps.
• Try $ n = 16, 17, \ldots, 24$ and see how many steps those take.
• Here is the process for $11\times 2^{14}$ to get to $104250$.