Check whether a number can be represented by the product of two squares

0 0 6 minutes read

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 2² * 6² = 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>

Output:

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>

Output:

No

Time Complexity: O(sqrt n)

Auxiliary Space: O(sqrt n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!