Java Coding Test Course, Finding Non-Square Numbers

Coding tests are an essential part of modern software development. Especially in object-oriented languages like Java, it is crucial to develop algorithm problem-solving skills. In this course, we will address the algorithm problem titled ‘Finding Non-Perfect Squares’. This problem involves finding the remaining numbers in an integer array excluding the perfect squares.

Problem Description

This problem requires identifying non-perfect square numbers from a given integer array. A perfect square is a number that results from squaring an integer, such as 0, 1, 4, 9, 16, ....

Input

  • An integer N is given (1 ≤ N ≤ 10000)
  • An array containing N integers is provided.

Output

  • A new array composed of integers from the original array that are not perfect squares is returned.

Problem-Solving Strategy

To solve this problem, we will follow these steps:

  1. Iterate through the array to check if each number is a perfect square.
  2. If it is not a perfect square, add it to a new array.
  3. Return the result array.

How to Check for Perfect Square

To determine if a number x is a perfect square, you can first calculate the square root of x and then convert that square root into an integer and square it again. If it matches x, then x is a perfect square.

boolean isPerfectSquare(int x) {
        if (x < 0) return false;
        int s = (int) Math.sqrt(x);
        return s * s == x;
}

Java Implementation

Now we will implement this algorithm in Java.

import java.util.ArrayList;
import java.util.List;

public class FindNonPerfectSquares {
    
    public static List<Integer> findNonPerfectSquares(int[] arr) {
        List<Integer> result = new ArrayList<>();

        for (int num : arr) {
            if (!isPerfectSquare(num)) {
                result.add(num);
            }
        }
        
        return result;
    }
    
    private static boolean isPerfectSquare(int x) {
        if (x < 0) return false;
        int s = (int) Math.sqrt(x);
        return s * s == x;
    }

    public static void main(String[] args) {
        int[] inputArray = {1, 2, 3, 4, 5, 9, 10, 15, 16, 20};
        List<Integer> nonPerfectSquares = findNonPerfectSquares(inputArray);
        System.out.println("Non-perfect squares: " + nonPerfectSquares);
    }
}

Code Explanation

The above code iterates through the provided array using a method called findNonPerfectSquares. For each number, it calls the isPerfectSquare method to skip perfect squares and adds only non-perfect squares to the result list.

Testing

Let’s run the code in practice. The main method defines a test input array, calls the function, and outputs the list of non-perfect squares.

Result Analysis

From the input array {1, 2, 3, 4, 5, 9, 10, 15, 16, 20}, the non-perfect squares are {2, 3, 5, 10, 15, 20}. This is an important step to verify the accuracy of the algorithm.

Complexity Analysis

The time complexity of this algorithm is O(N), as it traverses the array just once. The space complexity is also O(N) in the worst case due to the space required to store the result list.

Conclusion

In this lecture, we tackled the algorithm problem of finding non-perfect squares. Through this problem, we learned a basic method for solving algorithm problems by iterating through an array and adding values based on conditions. It is important to consistently practice solving such problems in preparation for various algorithm challenges that frequently appear.

In the next lecture, we will address more complex algorithm problems. Thank you!