Count Perfect Squares in an Array

Title: Count Perfect Squares in an Array

In this guide, you’ll learn how to count the number of perfect squares inside an integer array in Java. A perfect square is a non-negative integer whose integer square root, when multiplied by itself, returns the original value, for example 0, 1, 4, 9, 16, and 25. The problem is a classic warm-up because it combines a one-pass array scan with a small amount of math, and it shows up often in beginner level coding interviews.

Let’s explore how to design the solution together. We will frame the requirements, work out an approach, write a complete Java program, trace it on a fresh input, and finish with common mistakes and interview follow-ups you should expect.

Understanding the Problem

We are given an integer array and must return how many of its elements are perfect squares. Formally, an integer n is a perfect square when there exists a non-negative integer r such that r * r equals n. For instance, 25 is a perfect square because 5 * 5 equals 25, while 20 is not because no integer squared equals 20.

We also need to agree on how to treat the boundary values. We will count 0 and 1 as perfect squares since 0 * 0 is 0 and 1 * 1 is 1. We will skip negative numbers because no real integer squared can be negative. The algorithm should run in a single linear pass over the array.

Approach

The plan is to walk the array once and test each element with a cheap arithmetic check that reuses Math.sqrt. The steps below spell out the algorithm.

1. Reject a null array by throwing IllegalArgumentException so the caller sees the mistake instead of a NullPointerException.
2. Initialize a counter count to 0.
3. Iterate over every element value in the array using an enhanced for loop.
4. If value is negative, skip it with continue since negative integers cannot be perfect squares.
5. Compute root as (int) Math.sqrt(value) to grab the candidate integer root.
6. If root * root equals value, increment count.
7. After the loop ends, return count as the final answer.

Java Program

public class CountPerfectSquares {

    public static int countPerfectSquares(int[] numbers) {
        if (numbers == null) {
            throw new IllegalArgumentException("Input array must not be null");
        }
        int count = 0;
        for (int value : numbers) {
            if (value < 0) {
                continue;
            }
            int root = (int) Math.sqrt(value);
            if (root * root == value) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] numbers = {4, 7, 16, 23, 25, 30, 36};
        int total = countPerfectSquares(numbers);
        System.out.println("Perfect squares in the array: " + total);
    }
}

Explanation of the Program

The class CountPerfectSquares wraps a single public static method countPerfectSquares and a main driver. The method takes an int array and returns an int. Each line of the body plays a specific role.

• The null check at the top refuses a malformed input by throwing IllegalArgumentException so the problem surfaces at the call site rather than deep inside the loop.
• The counter count is zero before the loop starts and only grows when a match is found, which keeps the state easy to reason about.
• The enhanced for loop reads each element without an index, which keeps the body focused on the test rather than on bookkeeping.
• Negative values are skipped early with continue so Math.sqrt never receives a negative argument.
• Math.sqrt returns a double, and the cast to int truncates toward zero to produce the candidate integer root.
• Multiplying root by itself and comparing with value avoids floating point surprises; it either matches exactly or it does not.
• The main method prints the final count on a hand-picked input so you can run the program and see the result immediately.

Step-by-Step Trace

Let’s trace the algorithm on the input [2, 9, 14, 25, 49], where three elements (9, 25, and 49) are perfect squares and the final count should be 3.

At the end of iteration i, count holds the number of perfect squares seen in numbers[0..i-1]. When the loop exits, count equals the total answer for the whole array.

Examples

Here are two short examples you can run against the countPerfectSquares method to confirm the behavior on different inputs.

Example 1: Mixed positive integers

An array with a few perfect squares scattered among non-squares. The method must find each square exactly once.

int[] arr = {1, 2, 4, 9, 10, 16};
int result = countPerfectSquares(arr);
// Perfect squares present: 1, 4, 9, 16
// Output: 4

Example 2: Array containing zero

This example checks that the method treats 0 as a perfect square and handles larger squares like 36 and 64 correctly.

int[] arr = {0, 3, 5, 36, 64};
int result = countPerfectSquares(arr);
// Perfect squares present: 0, 36, 64
// Output: 3

Common Mistakes to Avoid

A few traps catch learners when they first write this routine. Watch out for the following, ordered from the most frequent to the most subtle.

• Trusting Math.sqrt alone – comparing Math.sqrt(value) == (int) Math.sqrt(value) fails for values like 2147395600 because double arithmetic loses precision near the top of the int range. Always finish with root * root == value.
• Rounding instead of truncating – using Math.round or Math.ceil on the result of Math.sqrt can push the candidate root one step away from the true integer root. Prefer (int) Math.sqrt(value) and then verify with multiplication.
• Counting negatives as squares – a check like value * value == value treats everything oddly, and forgetting the negative guard lets a negative number flow into Math.sqrt, which returns NaN. Add if (value < 0) continue; before the sqrt call.
• Forgetting zero – initializing root = 1 or starting the comparison from 1 silently drops 0 from the count. Let the generic root * root == value check accept 0 naturally.

Edge Cases to Test

Mention these inputs out loud during an interview so you cover the boundary conditions by habit.

• Empty array
• Single-element array
• Array of only perfect squares
• Array of no perfect squares
• Array containing 0 and 1
• Array containing only negative numbers
• Integer.MAX_VALUE present
• Null array reference

Additional Considerations

The time complexity is O(n) because we touch each element once and the per-element work is constant: a Math.sqrt call, a multiplication, and a comparison. On a modern JVM, Math.sqrt compiles down to a hardware instruction, so even millions of elements process in a few milliseconds.

The space complexity is O(1) extra memory. We hold count, value, and root at a time; no auxiliary structure grows with the input size. That makes the solution well suited to large arrays and streaming scenarios where memory is tight.

If accuracy matters at the extremes, remember that Math.sqrt returns a double with 53 bits of mantissa. For int inputs that is more than enough, but once you move to long inputs beyond 2^53 you should switch to an integer square root routine such as Newton’s method to avoid rounding error entirely.

Interview Follow-up Questions

Interviewers often probe deeper once the base solution works. Be ready for questions like these.

• What if you need to return the perfect squares themselves, not just the count? – replace the counter with an ArrayList<Integer> and add value to it inside the inner if; the time stays O(n) and the extra space becomes O(k) for k matches.
• What if the input arrives as a stream of unknown length? – keep the same per-element check and maintain a running count; termination now comes from end-of-stream rather than from the array length.
• What if the array contains long values up to 10^18? – replace Math.sqrt with a Newton iteration on long so double precision never bites you near the upper range.
• What if the array has billions of elements and does not fit in memory? – partition the input, count perfect squares in each partition independently, and sum the partial counts. The partition step is embarrassingly parallel.

Conclusion

Counting perfect squares in an array boils down to a single linear scan with a tight check: skip negatives, take the integer square root, and verify by multiplying it back. Writing the test as root * root == value keeps the logic safe from floating point drift and makes the intent obvious to any reviewer.

Try adapting the code to list the matched values, handle long inputs, or process a stream; each twist exercises a different muscle. You can learn more about similar problems on our Arrays category page: https://dailyjavaconcept.com/category/arrays/.