Given two integers, X and K, the task is to find if X2 is divisible by K or not. Here, both K and X can lie in the range [1,1018].
Examples:
Input: X = 6, K = 9
Output: YES
Explanation:
Since 62 is equal to 36, which is divisible by 9.Input: X = 7, K = 21
Output: NO
Explanation:
Since 72 is equal to 49, which is not divisible by 21.
Approach:
As mentioned above, X can lie in the range [1,1018], so we can not directly check if X2 is divisible by K or not as it can cause a memory overflow. Hence the efficient approach is to first calculate the Greatest Common Divisor of X and K. After the GCD is calculated, we will take it as the maximum portion which we can divide from X and K. Reduce K by GCD and check if X is divisible by the reduced K or not.
Below is the implementation of above approach:
C++
// C++ implementation to // check if the square of X is// divisible by K#include <bits/stdc++.h>using namespace std;// Function to return if // square of X is divisible // by Kvoid checkDivisible(int x, int k){ // Finding gcd of x and k int g = __gcd(x, k); // Dividing k by their gcd k /= g; // Check for divisibility of X // by reduced K if (x % k == 0) { cout << "YES\n"; } else { cout << "NO\n"; }}// Driver Codeint main(){ int x = 6, k = 9; checkDivisible(x, k); return 0;} |
Java
// Java implementation to // check if the square of X is// divisible by Kclass GFG{// Function to return if // square of X is divisible // by Kstatic void checkDivisible(int x, int k){ // Finding gcd of x and k int g = __gcd(x, k); // Dividing k by their gcd k /= g; // Check for divisibility of X // by reduced K if (x % k == 0) { System.out.print("YES\n"); } else { System.out.print("NO\n"); }}static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); }// Driver Codepublic static void main(String[] args){ int x = 6, k = 9; checkDivisible(x, k);}}// This code is contributed by gauravrajput1 |
Python3
# Python3 implementation to # check if the square of X is# divisible by Kfrom math import gcd# Function to return if # square of X is divisible # by Kdef checkDivisible(x, k): # Finding gcd of x and k g = gcd(x, k) # Dividing k by their gcd k //= g # Check for divisibility of X # by reduced K if (x % k == 0): print("YES") else: print("NO")# Driver Codeif __name__ == '__main__': x = 6 k = 9 checkDivisible(x, k); # This code is contributed by Bhupendra_Singh |
C#
// C# implementation to check// if the square of X is// divisible by Kusing System;class GFG{// Function to return if // square of X is divisible // by Kstatic void checkDivisible(int x, int k){ // Finding gcd of x and k int g = __gcd(x, k); // Dividing k by their gcd k /= g; // Check for divisibility of X // by reduced K if (x % k == 0) { Console.Write("YES\n"); } else { Console.Write("NO\n"); }}static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); }// Driver Codepublic static void Main(String[] args){ int x = 6, k = 9; checkDivisible(x, k);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation to // check if the square of X is// divisible by K// Return gcd of two numbersfunction gcd(a, b){ return b == 0 ? a : gcd(b, a % b);}// Function to return if // square of X is divisible // by Kfunction checkDivisible(x, k){ // Finding gcd of x and k var g = gcd(x, k); // Dividing k by their gcd k /= g; // Check for divisibility of X // by reduced K if (x % k == 0) { document.write("YES"); } else { document.write("NO"); }}// Driver codevar x = 6, k = 9; checkDivisible(x, k);// This code is contributed by Ankita saini </script> |
YES
Time Complexity: O(log(max(x, k)))
Auxiliary Space;:O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
