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

  1. Step 1: Start.
  2. Step 2: Set found = 0.
  3. Step 3: Read n.
  4. Step 4: Set i = 1.
  5. Step 5: If i * i <= n, go to step 6; otherwise go to step 9.
  6. Step 6: If i * i == n, go to step 7; otherwise go to step 8.
  7. Step 7: Set found = 1. Go to step 9.
  8. Step 8: Increase i by 1. Go to step 5.
  9. Step 9: If found == 1, go to step 10; otherwise go to step 11.
  10. Step 10: Print n is a perfect square. Go to step 12.
  11. Step 11: Print n is not a perfect square.
  12. 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)

StepLineBoxfoundniOutput
13Start
24found = 00
36Read n036Enter n:
47i = 10361
57i * i <= n?0361
68i * i == n?0361
77i++0362
87i * i <= n?0362
98i * i == n?0362
107i++0363
117i * i <= n?0363
128i * i == n?0363
137i++0364
147i * i <= n?0364
158i * i == n?0364
167i++0365
177i * i <= n?0365
188i * i == n?0365
197i++0366
207i * i <= n?0366

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.

More programs

← All programs

Try AI Flowchart free →