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;
Input: n = 4, k = 5184, a = 2, b = 3
Input: n = 5, k = 13, a = 2, b = 3
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.
Time Complexity: O(2^k)
Auxiliary Space: O(2^k)