Select Page

Convert N to K by multiplying by A or B in minimum steps

Kashish Kumar
Published: October 6, 2022

View Discussion

Improve Article

Save Article

Like Article

View Discussion

Improve Article

Save Article

Like Article

Given two numbers N and K, and a pair A and B, the task is to multiply N by A or B as many times to get K in minimum steps. If it is not possible to obtain K from N, return -1;

Examples:

Input: n = 4, k = 5184, a = 2, b = 3
Output: 8
Explanation: 4→12→24→72→144→432→1296→2592→5184

Input: n = 5, k = 13, a = 2, b = 3
Output: -1

Approach: The given problem can be solved by using recursion.

Follow the steps to solve this problem:

  • Initialize a count variable, Cnt = 0.
  • Call a recursive function to solve with a parameter n, k, a, b, Cnt.
  • Check, if n == k, return Cnt.
  • Else if, n > k, return INT_MAX;
  • Call, min(solve(a*n, k, a, b, Cnt + 1), solve(b*n, k, a, b, Cnt + 1)).
  • If, the return value is not equal to INT_MAX then print it else print -1.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

  

int solve(int n, int& k, int& a, int& b, int Cnt)

{

  

    if (n == k) {

        return Cnt;

    }

  

    if (n > k) {

        return INT_MAX;

    }

  

    return min(solve(a * n, k, a, b, Cnt + 1),

               solve(b * n, k, a, b, Cnt + 1));

}

  

int main()

{

  

    int n = 4;

    int k = 5184;

  

    int a = 2, b = 3;

  

    

    int res = solve(n, k, a, b, 0);

  

    if (res != INT_MAX)

        cout << res << endl;

    else

        cout << -1 << endl;

  

    return 0;

}

Time Complexity: O(2^k)
Auxiliary Space: O(2^k)

Source: www.geeksforgeeks.org