Problem Solving: Perfect Square Numbers
Learn to write a program that takes a stream of numbers and prints them whether a number is a complete square or not.
We'll cover the following
 Perfect square number
 Complete implementation
In this lesson, we will find whether a given number is a perfect square or not.
We will implement several implementations of this problem and stepbystep move towards better implementations. Keep in mind we are about to dive into looking at the following perspective: how do we write a program efficiently? Hence can we improve our implementation? So let’s start!
Perfect square number
Write and run a program that takes inputs until the user enters 1
and tells whether the input number is a perfect square or not.
Sample input
25 16 23 1
Sample output
25 is a perfect square
16 is a perfect square
23 is not a perfect square
A perfect square is a number that can be expressed as the product of an integer (let us call that number a verifier) by itself or as the second exponent of an integer. For example, 9 is a perfect square because $3 \times 3 = 3^2 = 9$
How do we find out whether a given number is a perfect square? Just think about the following question:
For a perfect square $S$, is it possible that the verifier $v$ is bigger then $S$ so that $v \times v=S$?
No $v$ cannot exceed $S$. This means one naive idea could be to just iterate through all the possible values of v lower than or equal to $S$ and check if the square of $v$ is equal to $S$.
Your task is to implement a function that checks whether the entered number is a perfect square or not. Let’s call this function isPerfectSquare()
, which returns true
if the parameter received is a perfect square and otherwise returns false
. For example, isPerfectSquare(25)
should return true
and isPerfectSquare(50)
should return false
.
Playground for your implementation
Write down your code in the following playground:
#include <iostream> using namespace std; bool isPerfectSquare(int num) { // Write your code here: } int main() { int num=0; cout << "Number to know is a perfect square : "; cin>>num; for(int cnt=0;num!=1;cnt++) { if(isPerfectSquare(num)) { cout<<" The number is a perfect square. \n"; } else { cout<<" The number is not a perfect square. \n"; } cout << "Number to know is a perfect square : "; cin>>num; } return 0; }
Implementations
Let us discuss several implementations.
Implementation 1: Naive version
Let’s look at perhaps the most naive idea.
Suppose we have the input number num
(e.g. 25) for testing to be a perfect square. We start the loop from 0
to num
, i.e. 25 for our example.
In each iteration, we will multiply each iteration value by itself and test if the square yields the given number, if it is so, we will set the test
variable to true
(which was set in the initialization as false
). After the loop ends, we will return the test variable (which will be holding whether a verifier was found or not).
So, our isPerfectSquare()
function looks like this:
bool isPerfectSquare(int num){bool test=false;for(int s=0;s<num;s++){if(s*s==num) // test will only be updated if there exists an s such that s*s = numtest=true;}return test;}
The main part should have a loop that takes numbers, one by one, in num
from the stream, Then in each iteration, we pass num
to an isPerfectSquare()
fucntion that checks num
is a perfect square or not, and displays the message accordingly.
Instruction: You can copy the isPerfectSquare()
function and click Run in the above playground.
Identifying inefficiency.
Have you noticed a slight flaw naivety with bool isPerfectSquare(int num)
? The above function completes an iteration of the for
loop, even though it has found that num
is a perfect square.
Look at these lines:
if(s*s==num)
test=true;
During the loop iteration, if the condition s*s==num
is true, it will execute test=true
. Hence, it has found that num
is a perfect square. Should we continue executing or should we stop?
Implementation 2: Using break
statement
Let us take advantage of the break
statement to stop the loop when we have found a perfect square. So our isPerfectSquare()
function will look like this:
bool isPerfectSquare(int num){bool test=false;for(int s=0;s<num;s++){if(s*s==num){test=true;break;}}return test;}
The program will return true
when it gets a perfect square. Not only this, but it also stops the loop immediately when it passes the perfect square test. This can be easily done by using the immediate return statement as well, Which can be seen in the second code (in tab).
Perfect square
What if a given number num
is not a perfect square? For example, if we pass 26
as an argument,how many times will the loop be executed?
Let us have a quiz regarding the above two implementations. We recommend pausing for a moment and rethinking what the code of isPerfectSquare()
is doing in the both above implementations.
If num
is 100, how many iterations will the isPerfectSquare()
function take in implementation 1?
100
10
Implementation 3: Reducing the range
For a large value of num
, running the iteration num
time. For example, is too much e.g., if the num
has a value close to $\approx 2^{30}$, and the num
is not a perfect square, then the loop will execute $\approx 2^{30}$ times. How can we reduce these iterations?
If the number is very large, let us say any number greater than 4, then we do not need to check for a perfect square above num/2
. For example, for num=101
, any value $v>=50$,$v^2$ will always be bigger than 101. Similarly, you may take any value of num
$\ge 4$. Hence, we can shrink the search space by half.
So our isPerfectSquare()
function is as follows:
bool isPerfectSquare(int num){for(int s=0;s<num/2;s++){if(s*s==num){return true; // function will return true when it gets the perfect square}}return false; // it will return false after num/2 iteration of loop}
Finding logical error
In implementation 3 let’s say we have num
having a value 0, 1 or 4. The output should be true
. However, what will be the output of the above function?
false
true
Exercise (fixing the logical error)
Add implementation 3 in the playground above and check for inputs 0
, 1
, or 4
. In all three cases, it should return true
. Modify the above implementation to fix the abovementioned bug.
Is there any other way to make implementation 3 more efficient? Take time and think about it.
Yes, we can make this function more efficient. That brings us to the next implementation.
Implementation 4: Efficient implementation
The idea is that, for each iteration, we check the following,

If we get a perfect square ,
s*s==num
, we returntrue.

Similarly, if we have
s*s<num
, then we should keep iterating and moving forward because the potential verifier could be found. 
However, what if
s*s>num
then Should we move forward, in searching for a verifier? The answer is ‘no’. This is because all the other values after thiss
will make their square even bigger thannum
. Hence, we should stop and returnfalse
immediately, because there is no verifier for this number.
Let’s write a function that is more efficient in using the above idea:
bool isPerfectSquare(int num){for(int s=0;s<num;s++){if(s*s==num)return true; // function will return true when he gets the perfect squareelse if(s*s > num)return false; // function will return false if a number is not perfect square}}
Instruction: Write the above code inside the playground and test it for a very big number like 1073741823 meaning $2^{30}1$ (you may verify it on a calculator).
Implementation 5: Find a logical error
Notice that in the following code, you will find an even simpler and more elegant implementation, but there is a small logical error that you need to fix.
Copy the code below and paste it into the above playground for execution.
Instruction: Executes the program stepbystep on a few inputs. For example, for 25, 26, 9, or 10.
bool isPerfectSquare(int num){int s;for(s=0; s*s <= num; s++){// This loop will end when s*s > num}return (s*s==num); // it will return true when s*s is equal to num}
Exercise: Fixing the bug
On the num=25
, it should have returned true
. However, it is returning false.Execute the code Step by step and fix the bug.
Comparison of implementations
If we look closely, implementations 1, 2, and 3 run around
n
times (wheren
is our number), implementations 4 and 5 execute around the square root ofn
times.How big of a difference is $n$ vs $\sqrt{n}$?
If we take a number as big as $2^{30}1$. Implementation 4 and 5 will be around $2^{15}$ times faster than the previous three implementations. This is a huge improvement. We can imagine that if implementations 4 and 5 take one second to execute for a big number, then the first three will take almost $2^{15}$ Seconds This is around 9.1 hours. This is a huge improvement.
Complete implementation
Below is the complete perfect square program with all the implementations.
#include <iostream>using namespace std;bool isPerfectSquareI1(int num){bool test=false;for(int s=0;s<num;s++){if(s*s==num) // test will only be updated if there exists an s such that s*s = numtest=true;}return test;}bool isPerfectSquareI2(int num){bool test=false;for(int s=0;s<num;s++){if(s*s==num){test=true;break;}}return test;}bool isPerfectSquareI3(int num){for(int s=0;s<num/2;s++){if(s*s==num){return true; // function will return true when it gets the perfect square}}return false; // it will return false after num/2 iteration of loop}bool isPerfectSquareI4(int num){for(int s=0;s<num;s++){if(s*s==num)return true; // function will return true when he gets the perfect squareelse if(s*s > num)return false; // function will return false if a number is not perfect square}}bool isPerfectSquareI5(int num){int s;for(s=0; s*s <= num; s++){// This loop will end when s*s > num}return ((s1)*(s1)==num);}int main(){int num=0;cout << "Number to check for perfect square (1 to stop): ";cin>>num; // num = 1073741823 (2^301)for(int cnt=0;num!=1;cnt++){if(isPerfectSquareI1(num))//if(isPerfectSquareI2(num))//if(isPerfectSquareI3(num))//if(isPerfectSquareI4(num))//if(isPerfectSquareI5(num)){cout<<num<<" is a perfect square. \n";}else{cout<<num<<" is not a perfect square. \n";}cout << "Number to check for perfect square (1 to stop): ";cin>>num;}return 0;}
Enter the input below
Instruction: Enter the values you want to check for perfect squares (ending with 1
) in the text box above. For example, 20 49 100 85 1
.
We hope that you’ve enjoyed this problem solving walkthrough, in which we first made the preliminary version of the program and then tweaked the code to make it more efficient. This is exactly how a programmer discovers the journey of reaching an elegant approach. We will follow the same approach of incrementally improving our program in the upcoming lessons too.