Perfect Square Check: flowchart, algorithm and program
This program reads a number n and tells you whether it is a perfect square. It tries i = 1, 2, 3, ... and checks if i × i equals n, stopping as soon as i × i grows bigger than n.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Set found = 0.
- Step 3: Read n.
- Step 4: Set i = 1.
- Step 5: If i * i <= n, go to step 6; otherwise go to step 9.
- Step 6: If i * i == n, go to step 7; otherwise go to step 8.
- Step 7: Set found = 1. Go to step 9.
- Step 8: Increase i by 1. Go to step 5.
- Step 9: If found == 1, go to step 10; otherwise go to step 11.
- Step 10: Print n is a perfect square. Go to step 12.
- Step 11: Print n is not a perfect square.
- Step 12: Stop.
Program in C, Python and Java
Perfect Square Check program in C
#include <stdio.h>
int main() {
int n, i, found = 0;
printf("Enter n: ");
scanf("%d", &n);
for (i = 1; i * i <= n; i++) {
if (i * i == n) {
found = 1;
break;
}
}
if (found)
printf("%d is a perfect square\n", n);
else
printf("%d is not a perfect square\n", n);
return 0;
}Perfect Square Check program in Python
n = int(input("Enter n: "))
found = False
i = 1
while i * i <= n:
if i * i == n:
found = True
break
i += 1
if found:
print(n, "is a perfect square")
else:
print(n, "is not a perfect square")Perfect Square Check program in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter n: ");
int n = sc.nextInt();
boolean found = false;
for (int i = 1; i * i <= n; i++) {
if (i * i == n) {
found = true;
break;
}
}
if (found)
System.out.println(n + " is a perfect square");
else
System.out.println(n + " is not a perfect square");
}
}
Sample input: n = 36
Output: 36 is a perfect square
How it works
- Start with found = 0 and i = 1. The flag found remembers whether we ever hit an exact match.
- The loop condition i * i <= n keeps going only while the square of i has not passed n. Once i * i is greater than n, no larger i can ever give n, so we stop.
- Inside the loop, if i * i == n, we set found = 1 and break out right away, because the answer is already known.
- After the loop, we check found: if it is 1 we print 'is a perfect square', otherwise we print 'is not a perfect square'.
- For n = 36: i = 1 gives 1, i = 2 gives 4, i = 3 gives 9, i = 4 gives 16, i = 5 gives 25, i = 6 gives 36, which equals n, so found becomes 1 and the output is '36 is a perfect square'.
Dry run (trace table)
| Step | Line | Box | found | n | i | Output |
|---|---|---|---|---|---|---|
| 1 | 3 | Start | ||||
| 2 | 4 | found = 0 | 0 | |||
| 3 | 6 | Read n | 0 | 36 | Enter n: | |
| 4 | 7 | i = 1 | 0 | 36 | 1 | |
| 5 | 7 | i * i <= n? | 0 | 36 | 1 | |
| 6 | 8 | i * i == n? | 0 | 36 | 1 | |
| 7 | 7 | i++ | 0 | 36 | 2 | |
| 8 | 7 | i * i <= n? | 0 | 36 | 2 | |
| 9 | 8 | i * i == n? | 0 | 36 | 2 | |
| 10 | 7 | i++ | 0 | 36 | 3 | |
| 11 | 7 | i * i <= n? | 0 | 36 | 3 | |
| 12 | 8 | i * i == n? | 0 | 36 | 3 | |
| 13 | 7 | i++ | 0 | 36 | 4 | |
| 14 | 7 | i * i <= n? | 0 | 36 | 4 | |
| 15 | 8 | i * i == n? | 0 | 36 | 4 | |
| 16 | 7 | i++ | 0 | 36 | 5 | |
| 17 | 7 | i * i <= n? | 0 | 36 | 5 | |
| 18 | 8 | i * i == n? | 0 | 36 | 5 | |
| 19 | 7 | i++ | 0 | 36 | 6 | |
| 20 | 7 | i * i <= n? | 0 | 36 | 6 |
Time and space complexity
Time: O(√n) · Space: O(1). The loop runs at most √n times (until i*i exceeds n) doing constant work each time, using only a few variables.
Common mistakes
- Looping up to n instead of stopping when i * i > n. That still works but does far more steps than needed.
- Forgetting the found flag and printing the 'not a perfect square' message inside the loop, which prints it on every pass.
- Not thinking about n = 0 or negative numbers. With this code, the loop never runs for n <= 0, so they are reported as not perfect squares (even though 0 is technically a perfect square).
Viva questions
Q1. What is the purpose of the variable 'found' and why is it initialised to 0?
'found' is a flag that records whether a perfect square was detected. It starts at 0 (false) because we assume n is not a perfect square until the loop proves otherwise by setting it to 1.
Q2. Why does the loop condition use i * i <= n instead of i <= n?
Once i*i exceeds n, no larger i can give i*i == n, so there is no point continuing. This stops the loop at about sqrt(n) iterations instead of n.
Q3. What does the 'break' on line 10 do, and what would happen without it?
It exits the loop as soon as i*i equals n, since the answer is already known. Without it the program would still give the correct result because found stays 1, but it would do a few wasted iterations.
Q4. What does the program print for n = 0, n = 1 and a negative number like -4?
For n = 0 the loop never runs because 1*1 > 0, so it prints 'not a perfect square', even though 0 = 0*0 is mathematically a perfect square. For n = 1 it prints 'perfect square' since 1*1 == 1. For a negative n, the condition 1 <= n is false so the loop is skipped and it prints 'not a perfect square', which is correct.
Q5. What is the time complexity of this program and why?
O(sqrt(n)), because i goes up from 1 only until i*i exceeds n, which takes about sqrt(n) steps. Space used is O(1).
Q6. Is there any risk with i * i <= n when n is very large, for example close to INT_MAX?
Yes. When n is near INT_MAX, i*i can exceed the range of int before the condition turns false, causing signed integer overflow, which is undefined behaviour. Using long long for i, or testing i <= n / i, avoids this.
Q7. What would you change so that n = 0 is also reported as a perfect square?
Start the loop at i = 0 so that 0*0 == 0 is tested, or add a special check 'if (n == 0) found = 1'. The rest of the logic can stay the same.
Q8. What other methods could you use to check for a perfect square, and how do they compare?
You can take r = (int)sqrt(n) from math.h and check r*r == n, which is O(1) but depends on floating-point accuracy. Binary search on i between 1 and n gives O(log n) and avoids floating-point problems. The loop used here is the simplest and fine for small n.
Frequently asked questions
Why does the loop stop when i * i is greater than n?
Because i keeps increasing, so i * i only gets bigger. Once it passes n, no later value can equal n, so checking further is pointless.
Is there a faster way than trying every i?
Yes. You can take the square root with sqrt() and check if its square equals n, or use binary search on i. The loop method is simpler and fine for small n.
Can i * i overflow for large n?
Yes. If n is close to the maximum int, i * i can exceed the int range before the loop ends. Using long long for i and the product avoids this.