Check if X and Y can be equal in N steps by dividing them with their factors
Given positive integers, X, Y, and N, the task is to check whether X can be made equal to Y in exactly N operations wherein each operation:
- X can be divided by any of its factors other than 1.
- Y can be divided by any of its factors other than 1.
Examples:
Input: X = 4, Y = 21, N = 3
Output: Yes
Explanation: Both X and Y can be made equal by doing the following operations:
X = X/4, Y = Y/3, Y = Y/7 which results in both X and Y as 1.
There are several other ways also to make both equal in three operations.
Like X = X/2, X = X/2, Y = Y/21.Input: X = 5, Y = 17, N = 3
Output: No
Approach: The idea to solve the problem is based on the following observation:
- The problem can be solved by making both the numbers 1.
- Minimum number of times to divide a number to get 1 is to divide the number by itself. And the maximum number of times to get 1 is the sum of exponents of all prime factors.
- Any natural number N can be written in terms of the product of its prime factors as:
N = p1n1.p2n2. . . pknk, where p1, p2 . . . pk are distinct prime numbers.- So the maximum number of times N can be divided is equal to n1 + n2 + …. + nk.
- If the maximum divisor of both X and Y combined is greater or equal to N, both can be made equal otherwise not.
Follow the steps mentioned below to implement the above observation:
- If N is equal to 1:
- If one among X and Y is the factor of the other, then they can be made equal.
- Otherwise, they cannot be made equal.
- Otherwise, if N is less than or equal to the maximum number of factors of X and Y then they can be made equal.
- Otherwise, no solution is possible.
Below is the implementation of the above approach in an optimized way:
C++
// C++ code to implement above approach #include <bits/stdc++.h> using namespace std; // Function to find total // number of times we can // divide a number before making it 1. int count( int val) { int ans = 0; // Checking how many times // the number can be // divided by 2. while (val % 2 == 0) { ans++; val = val / 2; } // Iterating through each number from // 3 to sqrt(val) and finding how many // times the number can be divide for ( int i = 3; i <= sqrt (val); i = i + 2) { while (val % i == 0) { ans++; val = val / i; } } if (val > 2) ans++; return ans; } // Function to return if // we can make x and y equal or not int solve( int x, int y, int n) { if (n == 0) { if (x == y) { cout << "Yes" ; } else { cout << "No" ; } } else if (n == 1) { if ((x % y == 0 || y % x == 0) && x != y) { cout << "Yes" ; } else { cout << "No" ; } } else { if (count(x) + count(y) >= n) { cout << "Yes" ; } else { cout << "No" ; } } } // Driver code int main() { int X = 4, Y = 21, N = 3; // Function call solve(X, Y, N); return 0; } |
Java
// Java code to implement above approach import java.io.*; class GFG { // Function to find total // number of times we can // divide a number before making it 1. static int count( int val) { int ans = 0 ; // Checking how many times // the number can be // divided by 2. while (val % 2 == 0 ) { ans++; val = val / 2 ; } // Iterating through each number from // 3 to sqrt(val) and finding how many // times the number can be divide for ( int i = 3 ; i <= Math.sqrt(val); i = i + 2 ) { while (val % i == 0 ) { ans++; val = val / i; } } if (val > 2 ) ans++; return ans; } // Function to return if // we can make x and y equal or not static void solve( int x, int y, int n) { if (n == 0 ) { if (x == y) { System.out.print( "Yes" ); } else { System.out.print( "No" ); } } else if (n == 1 ) { if ((x % y == 0 || y % x == 0 ) && x != y) { System.out.print( "Yes" ); } else { System.out.print( "No" ); } } else { if (count(x) + count(y) >= n) { System.out.print( "Yes" ); } else { System.out.print( "No" ); } } } // Driver code public static void main (String[] args) { int X = 4 , Y = 21 , N = 3 ; // Function call solve(X, Y, N); } } // This code is contributed by hrithikgarg03188. |
Python3
# Python3 code to implement above approach # Function to find total # number of times we can # divide a number before making it 1. def count(val): ans = 0 # Checking how many times # the number can be # divided by 2. while (val % 2 = = 0 ): ans + = 1 val = val / / 2 # Iterating through each number from # 3 to sqrt(val) and finding how many # times the number can be divide for i in range ( 3 , int (val * * 0.5 ) + 1 , 2 ): while (val % i = = 0 ): ans + = 1 val = val / / i if (val > 2 ): ans + = 1 return ans # Function to return if # we can make x and y equal or not def solve(x, y, n): if (n = = 0 ): if (x = = y): print ( "Yes" ) else : print ( "No" ) elif (n = = 1 ): if ((x % y = = 0 or y % x = = 0 ) and x ! = y): print ( "Yes" ) else : print ( "No" ) else : if (count(x) + count(y) > = n): print ( "Yes" ) else : print ( "No" ) # Driver code if __name__ = = "__main__" : x = 4 y = 21 n = 3 solve(x, y, n) # This code is contributed by amnindersingh1414. |
C#
// C# code to implement above approach using System; public class GFG { // Function to find total // number of times we can // divide a number before making it 1. static int count( int val) { int ans = 0; // Checking how many times // the number can be // divided by 2. while (val % 2 == 0) { ans++; val = val / 2; } // Iterating through each number from // 3 to sqrt(val) and finding how many // times the number can be divide for ( int i = 3; i <= Math.Sqrt(val); i = i + 2) { while (val % i == 0) { ans++; val = val / i; } } if (val > 2) ans++; return ans; } // Function to return if // we can make x and y equal or not static void solve( int x, int y, int n) { if (n == 0) { if (x == y) { Console.Write( "Yes" ); } else { Console.Write( "No" ); } } else if (n == 1) { if ((x % y == 0 || y % x == 0) && x != y) { Console.Write( "Yes" ); } else { Console.Write( "No" ); } } else { if (count(x) + count(y) >= n) { Console.Write( "Yes" ); } else { Console.Write( "No" ); } } } // Driver code public static int Main() { int X = 4, Y = 21, N = 3; // Function call solve(X, Y, N); return 0; } } // This code is contributed by Taranpreet |
Javascript
<script> // JavaScript code to implement above approach // Function to find total // number of times we can // divide a number before making it 1. const count = (val) => { let ans = 0; // Checking how many times // the number can be // divided by 2. while (val % 2 == 0) { ans++; val = parseInt(val / 2); } // Iterating through each number from // 3 to sqrt(val) and finding how many // times the number can be divide for (let i = 3; i <= parseInt(Math.sqrt(val)); i = i + 2) { while (val % i == 0) { ans++; val = parseInt(val / i); } } if (val > 2) ans++; return ans; } // Function to return if // we can make x and y equal or not const solve = (x, y, n) => { if (n == 0) { if (x == y) { document.write( "Yes" ); } else { document.write( "No" ); } } else if (n == 1) { if ((x % y == 0 || y % x == 0) && x != y) { document.write( "Yes" ); } else { document.write( "No" ); } } else { if (count(x) + count(y) >= n) { document.write( "Yes" ); } else { document.write( "No" ); } } } // Driver code let X = 4, Y = 21, N = 3; // Function call solve(X, Y, N); // This code is contributed by rakeshsahni </script> |
Output
Yes
Time complexity: O(√X)+ √Y)
Auxiliary Space: O(1)