Select Page

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

Kashish Kumar
Published: October 6, 2022

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 ``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