Select Page

Make two numbers equal in at most K steps dividing by their factor

Kashish Kumar
Published: June 17, 2022

View Discussion

Improve Article

Save Article

Like Article

Given integers X, Y, and K, the task is to make X and Y equal in not more than K operations by applying the following operations:

  • Choose an integer A and make X = X/A, (where A is an integer that is greater than 1 and not equal to X).
  • Choose an integer A and make Y = Y/A, (where A is an integer that is greater than 1 and not equal to Y).

Examples:

Input: X = 10, Y = 20, K = 4
Output: YES
Explanation: One optimal solution to make them equal is:
First choose A = 2 and do X = X/2 so now X is equal to 5.
Now choose A = 4 and do Y = Y/4 so now Y is equal to 5.
Since we have applied only two operations here which is less than K 
to make X and Y equal and also greater than one.
Therefore the answer is YES.

Input: X = 2, Y = 27, K = 1
Output: NO
Explanation: There is no possible way to make X and Y equal 
in less than or equal to 1 Operation.

 

Approach: To solve the problem follow the below idea:

Here are only two cases possible:

  • When K is equal to one and 
  • When K is greater than 1

If K is equal to one then it is possible to make X and Y equal only when either X is divisible by Y or Y is divisible by X

If K is greater than 1 then X and Y can be equal and greater than 1 only when their GCD is greater than 1.

Follow the steps mentioned below to implement the idea:

  • Check if K = 1:
    • In that case, find out if any of them is a divisor of the other.
  • Otherwise, find the GCD of the numbers.
    • If the GCD is 1 then it is not possible.
    • Otherwise, an answer always exists.

Below is the implementation for the above approach:

C++

  

#include <bits/stdc++.h>

using namespace std;

  

bool isPossible(int X, int Y, int K)

{

    

    if (K == 1) {

        if (X % Y == 0 || Y % X == 0)

            return true;

        return false;

    }

  

    

    else {

        if (__gcd(X, Y) > 1)

            return true;

        return false;

    }

    return false;

}

  

int main()

{

    int X = 10;

    int Y = 20;

    int K = 4;

  

    

    bool answer = isPossible(X, Y, K);

    if (answer)

        cout << "YES";

    else

        cout << "NO";

    return 0;

}

Time Complexity: O(1)
Auxiliary Space: O(1)

Source: www.geeksforgeeks.org