Check if given number is perfect square

Last Updated : 17 Sep, 2024

Given a number n, check if it is a perfect square or not.

Examples :

Input : n = 36
Output : Yes
Input : n = 2500
Output : Yes
Explanation: 2500 is a perfect square of 50
Input : n = 8
Output : No

Table of Content

Using sqrt()

Take the floor()ed square root of the number.
Multiply the square root twice.
Use boolean equal operator to verify if the product of square root is equal to the number given.

Code Implementation:

C++

// CPP program to find if x is a // perfect square. #include <bits/stdc++.h> using namespace std; bool isPerfectSquare(long long x) {  // Find floating point value of  // square root of x.  if (x >= 0) {  long long sr = sqrt(x);    // if product of square root   //is equal, then  // return T/F  return (sr * sr == x);  }  // else return false if n<0  return false; } int main() {  long long x = 49;  if (isPerfectSquare(x))  cout << "Yes";  else  cout << "No";  return 0; }

// C program to find if x is a // perfect square. #include <stdio.h> #include <math.h> int isPerfectSquare(long long x) {  // Find floating point value of  // square root of x.  if (x >= 0) {  long long sr = sqrt(x);  // if product of square root  // is equal, then  // return T/F  return (sr * sr == x);  }  // else return false if n<0  return 0; } int main() {  long long x = 49;  if (isPerfectSquare(x))  printf("Yes");  else  printf("No");  return 0; }

Java

// Java program to find if x is a perfect square. public class GfG {  public static boolean isPerfectSquare(long x)  {  // Find floating point value of  // square root of x.  if (x >= 0) {  long sr = (long)Math.sqrt(x);  // if product of square root  // is equal, then  // return T/F  return (sr * sr == x);  }  // else return false if n<0  return false;  }  public static void main(String[] args)  {  long x = 49;  if (isPerfectSquare(x))  System.out.println("Yes");  else  System.out.println("No");  } }

Python

# Python program to find if x is a # perfect square. def is_perfect_square(x): # Find floating point value of # square root of x. if x >= 0: sr = int(x ** 0.5) # if product of square root # is equal, then # return T/F return (sr * sr == x) # else return false if n<0 return False x = 49 if is_perfect_square(x): print("Yes") else: print("No")

// C# program to find if x is a // perfect square. using System; class GfG {  static bool IsPerfectSquare(long x) {  // Find floating point value of  // square root of x.  if (x >= 0) {  long sr = (long) Math.Sqrt(x);  // if product of square root  // is equal, then  // return T/F  return (sr * sr == x);  }  // else return false if n<0  return false;  }  static void Main() {  long x = 49;  if (IsPerfectSquare(x))  Console.WriteLine("Yes");  else  Console.WriteLine("No");  } }

JavaScript

// JavaScript program to find if x is a // perfect square. function isPerfectSquare(x) {  // Find floating point value of  // square root of x.  if (x >= 0) {  let sr = Math.floor(Math.sqrt(x));  // if product of square root  // is equal, then  // return T/F  return (sr * sr === x);  }  // else return false if n<0  return false; } const x = 49; if (isPerfectSquare(x))  console.log("Yes"); else  console.log("No");

Output

Yes

Time Complexity: O(log(x))
Auxiliary Space: O(1)

Using ceil, floor and sqrt() functions

Use the floor and ceil and sqrt() function.
If they are equal that implies the number is a perfect square.

Code Implementation:

C++

#include <bits/stdc++.h> using namespace std; bool isPerfectSquare(long long n) {  // If ceil and floor are equal  // the number is a perfect  // square  if (ceil((double)sqrt(n)) == floor((double)sqrt(n))){  return true;  }  else{  return false;  } } int main() {  long long x = 49;  if (isPerfectSquare(x))  cout << "Yes";  else  cout << "No";  return 0; }

#include <stdio.h> #include <math.h> // If ceil and floor are equal // the number is a perfect // square int isPerfectSquare(long long n) {  if (ceil((double)sqrt(n)) == floor((double)sqrt(n))) {  return 1; // true  }  else {  return 0; // false  } } int main() {  long long x = 49;  if (isPerfectSquare(x))  printf("Yes");  else  printf("No");  return 0; }

Java

public class GfG {  public static boolean isPerfectSquare(long n) {  // If ceil and floor are equal  // the number is a perfect  // square  if (Math.ceil(Math.sqrt(n)) == Math.floor(Math.sqrt(n))) {  return true;  } else {  return false;  }  }  public static void main(String[] args) {  long x = 49;  if (isPerfectSquare(x))  System.out.println("Yes");  else  System.out.println("No");  } }

Python

import math def is_perfect_square(n): # If ceil and floor are equal # the number is a perfect # square if math.ceil(math.sqrt(n)) == math.floor(math.sqrt(n)): return True else: return False x = 49 if is_perfect_square(x): print("Yes") else: print("No")

using System; class GfG {  public static bool IsPerfectSquare(long n) {  // If ceil and floor are equal  // the number is a perfect  // square  if (Math.Ceiling(Math.Sqrt(n)) == Math.Floor(Math.Sqrt(n))) {  return true;  } else {  return false;  }  }  static void Main() {  long x = 49;  if (IsPerfectSquare(x))  Console.WriteLine("Yes");  else  Console.WriteLine("No");  } }

JavaScript

function isPerfectSquare(n) {  // If ceil and floor are equal  // the number is a perfect  // square  if (Math.ceil(Math.sqrt(n)) === Math.floor(Math.sqrt(n))) {  return true;  } else {  return false;  } } const x = 49; if (isPerfectSquare(x)) {  console.log("Yes"); } else {  console.log("No"); }

Output

Yes

Time Complexity : O(sqrt(n))
Auxiliary space: O(1)

Using Binary search:

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std; // Function to check if a number is a perfect square using // binary search bool isPerfectSquare(long long n) {  // Base case: 0 and 1 are perfect squares  if (n <= 1) {  return true;  }  // Initialize boundaries for binary search  long long left = 1, right = n;  while (left <= right) {  // Calculate middle value  long long mid = left + (right - left) / 2;  // Calculate square of the middle value  long long square = mid * mid;  // If the square matches n, n is a perfect square  if (square == n) {  return true;  }  // If the square is smaller than n, search the right  // half  else if (square < n) {  left = mid + 1;  }  // If the square is larger than n, search the left  // half  else {  right = mid - 1;  }  }  // If the loop completes without finding a perfect  // square, n is not a perfect square  return false; } int main() {  long long x = 49;  if (isPerfectSquare(x))  cout << "Yes";  else  cout << "No";  return 0; }

#include <stdio.h> // Function to check if a number is a perfect square using // binary search int isPerfectSquare(long long n) {  // Base case: 0 and 1 are perfect squares  if (n <= 1) {  return 1;  }  // Initialize boundaries for binary search  long long left = 1, right = n;  while (left <= right) {  // Calculate middle value  long long mid = left + (right - left) / 2;  // Calculate square of the middle value  long long square = mid * mid;  // If the square matches n, n is a perfect square  if (square == n) {  return 1;  }  // If the square is smaller than n, search the right half  else if (square < n) {  left = mid + 1;  }  // If the square is larger than n, search the left half  else {  right = mid - 1;  }  }  // If the loop completes without finding a perfect square, n is not a perfect square  return 0; } int main() {  long long x = 49;  if (isPerfectSquare(x))  printf("Yes");  else  printf("No");  return 0; }

Java

public class GfG {  // Function to check if a number is a perfect square using  // binary search  public static boolean isPerfectSquare(long n) {  // Base case: 0 and 1 are perfect squares  if (n <= 1) {  return true;  }  // Initialize boundaries for binary search  long left = 1, right = n;  while (left <= right) {  // Calculate middle value  long mid = left + (right - left) / 2;  // Calculate square of the middle value  long square = mid * mid;  // If the square matches n, n is a perfect square  if (square == n) {  return true;  }  // If the square is smaller than n, search the right  // half  else if (square < n) {  left = mid + 1;  }  // If the square is larger than n, search the left  // half  else {  right = mid - 1;  }  }  // If the loop completes without finding a perfect  // square, n is not a perfect square  return false;  }  public static void main(String[] args) {  long x = 49;  if (isPerfectSquare(x))  System.out.println("Yes");  else  System.out.println("No");  } }

Python

def is_perfect_square(n): # Base case: 0 and 1 are perfect squares if n <= 1: return True # Initialize boundaries for binary search left, right = 1, n while left <= right: # Calculate middle value mid = left + (right - left) // 2 # Calculate square of the middle value square = mid * mid # If the square matches n, n is a perfect square if square == n: return True # If the square is smaller than n, search the right half elif square < n: left = mid + 1 # If the square is larger than n, search the left half else: right = mid - 1 # If the loop completes without finding a perfect square, n is not a perfect square return False x = 49 if is_perfect_square(x): print("Yes") else: print("No")

using System; class GfG {  // Function to check if a number is a perfect square using  // binary search  static bool IsPerfectSquare(long n) {  // Base case: 0 and 1 are perfect squares  if (n <= 1) {  return true;  }  // Initialize boundaries for binary search  long left = 1, right = n;  while (left <= right) {  // Calculate middle value  long mid = left + (right - left) / 2;  // Calculate square of the middle value  long square = mid * mid;  // If the square matches n, n is a perfect square  if (square == n) {  return true;  }  // If the square is smaller than n, search the right half  else if (square < n) {  left = mid + 1;  }  // If the square is larger than n, search the left half  else {  right = mid - 1;  }  }  // If the loop completes without finding a perfect square, n is not a perfect square  return false;  }  static void Main() {  long x = 49;  if (IsPerfectSquare(x))  Console.WriteLine("Yes");  else  Console.WriteLine("No");  } }

JavaScript

function isPerfectSquare(n) {  // Base case: 0 and 1 are perfect squares  if (n <= 1) {  return true;  }  // Initialize boundaries for binary search  let left = 1, right = n;  while (left <= right) {  // Calculate middle value  let mid = left + Math.floor((right - left) / 2);  // Calculate square of the middle value  let square = mid * mid;  // If the square matches n, n is a perfect square  if (square === n) {  return true;  }  // If the square is smaller than n, search the right half  else if (square < n) {  left = mid + 1;  }  // If the square is larger than n, search the left half  else {  right = mid - 1;  }  }  // If the loop completes without finding a perfect square, n is not a perfect square  return false; } const x = 49; if (isPerfectSquare(x)) {  console.log("Yes"); } else {  console.log("No"); }

Output

Yes

Time Complexity: O(log n)
Auxiliary Space: O(1)

Using Mathematical Properties:

The idea is based on the fact that perfect squares are always some of first few odd numbers.

1 + 3 = 4
1 + 3 + 5 = 9
1 + 3 + 5 + 7 = 16
1 + 3 + 5 + 7 + 9 = 25
1 + 3 + 5 + 7 + 9 + 11 = 36
......................................................

Code Implementation:

C++

#include <bits/stdc++.h> using namespace std; bool isPerfectSquare(long long n) {    // 0 is considered as a perfect  // square  if (n == 0) return true;   long long odd = 1; while (n > 0) { n -= odd; odd += 2; } return n == 0; } int main() {  long long x = 49;  if (isPerfectSquare(x))  cout << "Yes";  else  cout << "No";  return 0; }

#include <stdio.h> // 0 is considered as a perfect // square int isPerfectSquare(long long n) {  if (n == 0) return 1; // true  long long odd = 1;  while (n > 0) {  n -= odd;  odd += 2;  }  return n == 0; } int main() {  long long x = 49;  if (isPerfectSquare(x))  printf("Yes");  else  printf("No");  return 0; }

Java

public class GfG {  public static boolean isPerfectSquare(long n) {  // 0 is considered as a perfect  // square  if (n == 0) return true;  long odd = 1;  while (n > 0) {  n -= odd;  odd += 2;  }  return n == 0;  }  public static void main(String[] args) {  long x = 49;  if (isPerfectSquare(x))  System.out.println("Yes");  else  System.out.println("No");  } }

Python

def is_perfect_square(n): # 0 is considered as a perfect # square if n == 0: return True odd = 1 while n > 0: n -= odd odd += 2 return n == 0 x = 49 if is_perfect_square(x): print("Yes") else: print("No")

using System; class GfG {  public static bool IsPerfectSquare(long n) {  // 0 is considered as a perfect  // square  if (n == 0) return true;  long odd = 1;  while (n > 0) {  n -= odd;  odd += 2;  }  return n == 0;  }  static void Main() {  long x = 49;  if (IsPerfectSquare(x))  Console.WriteLine("Yes");  else  Console.WriteLine("No");  } }

JavaScript

function isPerfectSquare(n) {  // 0 is considered as a perfect  // square  if (n === 0) return true;  let odd = 1;  while (n > 0) {  n -= odd;  odd += 2;  }  return n === 0; } const x = 49; if (isPerfectSquare(x)) {  console.log("Yes"); } else {  console.log("No"); }

Output

Yes

How does this work?

1 + 3 + 5 + ... (2n-1) = Sum(2*i - 1) where 1<=i<=n
= 2*Sum(i) - Sum(1) where 1<=i<=n
= 2n(n+1)/2 - n
= n(n+1) - n
= n^2'

Time Complexity Analysis

Let us assume that the above loop runs i times. The following series would have i terms.

1 + 3 + 5 ........ = n [Let there be i terms]
1 + (1 + 2) + (1 + 2 + 2) + ........ = n [Let there be i terms]
(1 + 1 + ..... i-times) + (2 + 4 + 6 .... (i-1)-times) = n
i + (2^(i-1) - 1) = n
2^(i-1) = n + 1 - i
Using this expression, we can say that i is upper bounded by Log n