Check if a number is a perfect square
Given a positive number, check if it is a perfect square without using any built-in library function. A perfect square is a number that is the square of an integer.
For example,
Output: true
Explanation: 25 is a perfect square since it can be written as 5×5.
Input: n = 20
Output: false
Explanation: 20 is not the product of an integer with itself.
1. Using Perfect Square Property
Every perfect square satisfies the property that it is the sum of the odd numbers starting with one. For example,
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
25 = 1 + 3 + 5 + 7 + 9
…
n = 1 + 3 + 5 + … + (2*n-1)
We can make use of this property to determine if a number n is a perfect square or not. The idea is to repeatedly subtract odd numbers from n, starting from 1, until it becomes 0 or negative. If the value reaches 0 at some point, we can say that the number is a perfect square. However, if the value becomes negative without reaching 0, the number cannot be a perfect square. This is demonstrated below in C++, Java, and Python.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> #include <vector> using namespace std; bool isPerfectSquare(int n) { // start with the odd number 1 int odd = 1; // loop until the value is 0 or negative while (n > 0) { // subtract the next odd number from `n` n = n - odd; // take next odd number for the next iteration odd = odd + 2; } // only a perfect square will reach a value of 0 return n == 0; } int main() { int n = 25; cout << std::boolalpha << isPerfectSquare(n); return 0; } |
Output:
true
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Main { public static boolean isPerfectSquare(int n) { // start with the odd number 1 int odd = 1; // loop until the value is 0 or negative while (n > 0) { // subtract the next odd number from `n` n = n - odd; // take next odd number for the next iteration odd = odd + 2; } // only a perfect square will reach a value of 0 return n == 0; } public static void main(String[] args) { int n = 25; System.out.println(isPerfectSquare(n)); } } |
Output:
true
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
def isPerfectSquare(n): # start with the odd number 1 odd = 1 # loop until the value is 0 or negative while n > 0: n = n - odd # subtract the next odd number from `n` odd = odd + 2 # take next odd number for the next iteration # only a perfect square will reach a value of 0 return n == 0 if __name__ == '__main__': n = 25 print(isPerfectSquare(n)) |
Output:
True
The time complexity of the above procedure is O(n) and requires constant extra space, where n is the given number.
2. Using Binary Search
We can improve the time complexity of the solution to O(log(n)) by using a binary search algorithm. The idea is to start with the search space [low, high] = [0, n] and try to find a mid value that satisfies the condition mid × mid == n. Based on a comparison result between n and mid × mid, the procedure will increment low, decrement high, or return true if n is the product of mid with itself.
Here’s the C++, Java, and Python program that demonstrates it:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> #include <vector> using namespace std; bool isPerfectSquare(int n) { // set the search space to [0, n]. int low = 0, high = n; while (low <= high) { // calculate mid int mid = low + ((high - low)/2); // if `mid×mid` is equal to `n`, return true if (mid * mid == n) { return true; } // if `mid×mid` is less than `n`, update `low` to `mid + 1` if (mid * mid < n) { low = mid + 1; } // otherwise, update `high` to `mid - 1` else { high = mid - 1; } } // we reach this point if the number is not a perfect square return false; } int main() { int n = 25; cout << std::boolalpha << isPerfectSquare(n); return 0; } |
Output:
true
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Main { public static boolean isPerfectSquare(int n) { // set the search space to [0, n]. int low = 0, high = n; while (low <= high) { // calculate mid int mid = low + ((high - low)/2); // if `mid×mid` is equal to `n`, return true if (mid * mid == n) { return true; } // if `mid×mid` is less than `n`, update `low` to `mid + 1` if (mid * mid < n) { low = mid + 1; } // otherwise, update `high` to `mid - 1` else { high = mid - 1; } } // we reach this point if the number is not a perfect square return false; } public static void main(String[] args) { int n = 25; System.out.println(isPerfectSquare(n)); } } |
Output:
true
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
def isPerfectSquare(n): # set the search space to [0, n]. low, high = 0, n while low <= high: mid = int(low + ((high - low) / 2)) # calculate mid # if `mid×mid` is equal to `n`, return true if mid * mid == n: return True # if `mid×mid` is less than `n`, update `low` to `mid + 1` if mid * mid < n: low = mid + 1 # otherwise, update `high` to `mid - 1` else: high = mid - 1 # we reach this point if the number is not a perfect square return False if __name__ == '__main__': n = 25 print(isPerfectSquare(n)) |
Output:
True
3. Using Newton’s Method
Finally, we can use Newton’s method to compute square roots. The mathematical logic behind Newton’s method is outside the scope of this article. The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <iostream> #include <vector> using namespace std; bool isPerfectSquare(int n) { int i = n; while (i * i > n) { i = (i + n / i) / 2; } return i * i == n; } int main() { int n = 25; cout << std::boolalpha << isPerfectSquare(n); return 0; } |
Output:
true
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Main { public static boolean isPerfectSquare(int n) { int i = n; while (i * i > n) { i = (i + n / i) / 2; } return i * i == n; } public static void main(String[] args) { int n = 25; System.out.println(isPerfectSquare(n)); } } |
Output:
true
Python
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)