Given two integers P and Q, the task is to check whether a pair (P, Q) is equal or not, and a pair is said to be equal if there exist some positive integers X and Y such that PX = QY.
Examples:
Input: P = 16 , Q = 4
Output: Yes
?Explanation: Let X = 2 and Y = 4. Thus, PX = 162 = 256 and QY = 44 = 256 . Thus, the pair (16,4) is equal.Input: P = 12 , Q = 24
Output: No
Approach: The problem can be solved based on the following observation:
For PX = QY to be true for some integer pair (X, Y), any one of the below cases must be true:
- There must exist some integer K, such that
- P = KA
- Q = KB
- X = Y = 0
Now to implement this, below algorithm can be used:
- Find maximum(max) and minimum(min) number for two integer.
- Iterate a loop and check if max and min is equal or max is divisible by min, then pair of integer is equal and break from the loop.
- Otherwise, pair of integer is not equal.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to check whether a pair of// integer is equal or notvoid check(int p, int q){ int maxi = max(p, q); int mini = min(p, q); while (true) { if (maxi == mini) { cout << "Yes"; break; } if (maxi % mini != 0) { cout << "No"; break; } int temp = maxi / mini; maxi = max(temp, mini); mini = min(temp, mini); }}// Driver Codeint main(){ int P = 16; int Q = 4; // Function call check(P, Q); return 0;}// This code is contributed by aarohirai2616. |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;public class GFG { // Function to check whether a pair of // integer is equal or not public static void check(int p, int q) { int max = Math.max(p, q); int min = Math.min(p, q); while (true) { if (max == min) { System.out.println("Yes"); break; } if (max % min != 0) { System.out.println("No"); break; } int temp = max / min; max = Math.max(temp, min); min = Math.min(temp, min); } } // Driver code public static void main(String[] args) { int P = 16; int Q = 4; // Function call check(P, Q); }} |
Python3
# Python3 code to implement the above approach# Function to check whether a pair of# integer is equal or notdef check( p, q) : maxi = max(p, q); mini = min(p, q); while (True) : if (maxi == mini) : print("Yes"); break; if (maxi % mini != 0) : print("No"); break; temp = maxi // mini; maxi = max(temp, mini); mini = min(temp, mini);# Driver Codeif __name__ == "__main__" : P = 16; Q = 4; # Function call check(P, Q); # This code is contributed by AnkThon |
C#
// C# implementationusing System;public class GFG{ // Function to check whether a pair of // integer is equal or not public static void check(int p, int q) { int maxi = Math.Max(p, q); int mini = Math.Min(p, q); while (true) { if (maxi == mini) { Console.WriteLine("Yes"); break; } if (maxi % mini != 0) { Console.WriteLine("No"); break; } int temp = maxi / mini; maxi =Math.Max(temp, mini); mini =Math.Min(temp, mini); } } static public void Main (){ int P = 16; int Q = 4; // Function call check(P, Q); }}// This code is contributed by ksam24000 |
Javascript
// js code to implement the approach// Function to check whether a pair of// integer is equal or notfunction check (p, q){ let maxi = Math.max(p, q); let mini = Math.min(p, q); while (true) { if (maxi == mini) { console.log("Yes"); break; } if (maxi % mini != 0) { console.log("No"); break; } let temp = Math.floor(maxi / mini); maxi = Math.max(temp, mini); mini = Math.min(temp, mini); }}// Driver Code let P = 16; let Q = 4; // Function call check(P, Q);// This code is contributed by ksam24000. |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Take a part in the ongoing discussion
