Given two numbers N and Ok, and a pair A and B, the duty is to multiply N by A or B as many instances to get Ok in minimal steps. If it’s not doable to acquire Ok from N, return -1;
Examples:
Enter: n = 4, ok = 5184, a = 2, b = 3
Output: 8
Clarification: 4→12→24→72→144→432→1296→2592→5184Enter: n = 5, ok = 13, a = 2, b = 3
Output: -1
Method: The given downside will be solved by utilizing recursion.
Observe the steps to unravel this downside:
- Initialize a depend variable, Cnt = 0.
- Name a recursive perform to unravel with a parameter n, ok, a, b, Cnt.
- Examine, if n == ok, return Cnt.
- Else if, n > ok, return INT_MAX;
- Name, min(clear up(a*n, ok, a, b, Cnt + 1), clear up(b*n, ok, a, b, Cnt + 1)).
- If, the return worth is just not equal to INT_MAX then print it else print -1.
Under is the implementation of the above method.
C++
|
Time Complexity: O(2^ok)
Auxiliary Area: O(2^ok)