Thursday, October 6, 2022
HomeWordPress DevelopmentConvert N to Ok by multiplying by A or B in minimal...

Convert N to Ok by multiplying by A or B in minimal steps


View Dialogue

Enhance Article

Save Article

Like Article

View Dialogue

Enhance Article

Save Article

Like Article

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→5184

Enter: 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++

#embody <bits/stdc++.h>

utilizing namespace std;

  

int clear up(int n, int& ok, int& a, int& b, int Cnt)

{

  

    if (n == ok) {

        return Cnt;

    }

  

    if (n > ok) {

        return INT_MAX;

    }

  

    return min(clear up(a * n, ok, a, b, Cnt + 1),

               clear up(b * n, ok, a, b, Cnt + 1));

}

  

int principal()

{

  

    int n = 4;

    int ok = 5184;

  

    int a = 2, b = 3;

  

    

    int res = clear up(n, ok, a, b, 0);

  

    if (res != INT_MAX)

        cout << res << endl;

    else

        cout << -1 << endl;

  

    return 0;

}

Time Complexity: O(2^ok)
Auxiliary Area: O(2^ok)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments