Check whether a number can be represented by the product of two squares
Given an integer n, our task is to check whether number n can be represented by the product of two squares. If it is possible then print “yes” otherwise print “no”.
Examples :
Input: n = 144
Output: Yes
Explanation:
The given number 144 can be represented as 22 * 62 = 144.Input: n = 25
Output: No
Explanation:
The given number 25 cannot be represented as product of two square numbers.
Naive Approach:
To solve the problem mentioned above the naive method is to use the Brute Force method. Use two for loop iterating till n and each time we will check whether the product of the square of both numbers is equal to N. If we find such a combination then we will print Yes otherwise No.
Below is the implementation of above approach:
C++
// C++ implementation to Check whether a number can // be represented by the product of two squares #include <bits/stdc++.h> using namespace std; // Function to check if there exist two // numbers product of whose squares is n. bool prodSquare( int n) { for ( long i = 2; i * i <= n; i++) for ( long j = 2; j <= n; j++) // check whether the product of the square // of both numbers is equal to N if (i * i * j * j == n) return true ; return false ; } // Driver code int main() { int n = 25; if (prodSquare(n)) cout << "Yes" ; else cout << "No" ; } |
Java
// Java implementation to check whether a number can // be represented by the product of two squares class GFG{ // Function to check if there exist two // numbers product of whose squares is n. static boolean prodSquare( int n) { for ( long i = 2 ; i * i <= n; i++) for ( long j = 2 ; j <= n; j++) // Check whether the product of the square // of both numbers is equal to N if (i * i * j * j == n) return true ; return false ; } // Driver code public static void main(String[] args) { int n = 25 ; if (prodSquare(n)) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 implementation to check whether # a number can be represented by the # product of two squares # Function to check if there exist two # numbers product of whose squares is n. def prodSquare(n): for i in range ( 2 , (n) + 1 ): if (i * i < (n + 1 )): for j in range ( 2 , n + 1 ): # Check whether the product # of the square of both # numbers is equal to N if ((i * i * j * j) = = n): return True ; return False ; # Driver code if __name__ = = '__main__' : n = 25 ; if (prodSquare(n)): print ( "Yes" ); else : print ( "No" ); # This code is contributed by Rajput-Ji |
C#
// C# implementation to check whether // a number can be represented by // the product of two squares using System; class GFG{ // Function to check if there // exist two numbers product // of whose squares is n. static bool prodSquare( int n) { for ( long i = 2; i * i <= n; i++) for ( long j = 2; j <= n; j++) // Check whether the product // of the square of both // numbers is equal to N if (i * i * j * j == n) return true ; return false ; } // Driver code public static void Main(String[] args) { int n = 25; if (prodSquare(n)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // javascript implementation to check whether a number can // be represented by the product of two squares // Function to check if there exist two // numbers product of whose squares is n. function prodSquare(n) { for (i = 2; i * i <= n; i++) for (j = 2; j <= n; j++) // Check whether the product of the square // of both numbers is equal to N if (i * i * j * j == n) return true ; return false ; } // Driver code var n = 25; if (prodSquare(n)) document.write( "Yes" ); else document.write( "No" ); // This code contributed by Rajput-Ji </script> |
No
Time Complexity: O(n)
Auxiliary Space: O(1)
Efficient Approach:
To optimize the above method, use a hashmap where we will store the squares of number till sqrt(n) and each time we will search for (n / sqrt(i)) in the hashmap if it exists then return Yes else return No.
C++
// C++ implementation to Check whether a number can // be represented by the product of two squares #include <bits/stdc++.h> using namespace std; // Function to check if there exist two // numbers product of whose squares is n bool prodSquare( int n) { // Initialize map unordered_map< float , float > s; for ( int i = 2; i * i <= n; ++i) { // Store square value in hashmap s[i * i] = 1; if (s.find(n / (i * i)) != s.end()) return true ; } return false ; } // Driver code int main() { int n = 25; if (prodSquare(n)) cout << "Yes" ; else cout << "No" ; } |
Java
// Java implementation to check whether // a number can be represented by the // product of two squares import java.util.*; class GFG{ // Function to check if there exist two // numbers product of whose squares is n static boolean prodSquare( int n) { // Initialize map HashMap<Float, Float> s = new HashMap<Float, Float>(); for ( int i = 2 ; i * i <= n; ++i) { // Store square value in hashmap s.put(( float )(i * i), ( float ) 1 ); if (s.containsKey(( float ) n / (i * i))) return true ; } return false ; } // Driver code public static void main(String[] args) { int n = 25 ; if (prodSquare(n)) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to check whether # a number can be represented by the # product of two squares # Function to check if there exist two # numbers product of whose squares is n def prodSquare(n): # Initialize dict/map s = dict () i = 2 while (i * i < = n): # Store square value in hashmap s[i * i] = 1 if ((n / / (i * i)) in s): return True i + = 1 return False # Driver Code if __name__ = = '__main__' : n = 25 if (prodSquare(n)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by himanshu77 |
C#
// C# implementation to check whether // a number can be represented by the // product of two squares using System; using System.Collections.Generic; class GFG{ // Function to check if there exist two // numbers product of whose squares is n static bool prodSquare( int n) { // Initialize map Dictionary< float , float > s = new Dictionary< float , float >(); for ( int i = 2; i * i <= n; ++i) { // Store square value in hashmap s.Add(( float )(i * i), ( float ) 1); if (s.ContainsKey(( float ) n / (i * i))) return true ; } return false ; } // Driver code public static void Main(String[] args) { int n = 25; if (prodSquare(n)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by amal kumar choubey |
Javascript
<script> //Javascript implementation to check whether // K times of a element is present in // the array // Function to check if there exist two // numbers product of whose squares is n function prodSquare(n) { // Initialize map var s = new Map(); for ( var i = 2; i * i <= n; ++i) { // Store square value in hashmap s.set(i * i,1); if (s.has(n / (i * i))) return true ; } return false ; } // Driver program to test above var n = 25; if (prodSquare(n)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by shivani. </script> |
No
Time Complexity: O(sqrt n)
Auxiliary Space: O(sqrt n)
Contact Us