Kotlin coding test cource, Finding Non-Square Numbers

Hello! In this course, we will delve deeply into algorithm problems that are commonly encountered in coding tests using Kotlin. The topic is ‘Finding Non-Perfect Squares.’ The basic idea of this problem is to find all numbers that are not perfect squares (1, 4, 9, 16, etc.) within a given range. We will explore the algorithmic thinking and Kotlin syntax needed to understand and solve this problem.

Problem Description

The problem is as follows:

Finding Non-Perfect Squares
Write a function to find all numbers that are not perfect squares among natural numbers from 1 to N.

Input: Integer N (1 ≤ N ≤ 1000)
Output: List of non-perfect square numbers

Problem Analysis

To solve this problem, the following steps are necessary:

  • Iterate through all natural numbers from 1 to N.
  • Devise a method to check if each number is a perfect square.
  • Store the numbers that are not perfect squares in a list.

Perfect squares appear in the form of 1, 4, 9, 16, 25, … and these numbers are represented as i squared. Therefore, as i starts from 1 and increases to √N, we can store the squared result in a list. After that, we can include the remaining numbers, excluding these perfect squares, in the result list.

Algorithm Design

Based on the above process, the following algorithm can be designed:

  1. Create an empty list.
  2. Run a loop from 1 to N.
  3. Determine whether each number is a perfect square.
  4. If it is not a perfect square, add it to the list.
  5. Output the result list.

Kotlin Code Implementation

Now, let’s implement this algorithm in Kotlin:

fun findNonPerfectSquares(n: Int): List {
    val nonPerfectSquares = mutableListOf()
    
    // Set to store perfect squares
    val perfectSquares = mutableSetOf()
    
    // Calculate perfect squares from 1 to n
    for (i in 1..Math.sqrt(n.toDouble()).toInt()) {
        perfectSquares.add(i * i)
    }
    
    // Explore from 1 to N
    for (i in 1..n) {
        // Add to the list if it is not a perfect square
        if (i !in perfectSquares) {
            nonPerfectSquares.add(i)
        }
    }
    
    return nonPerfectSquares
}

In the above code, the findNonPerfectSquares function returns a list of numbers that are not perfect squares among natural numbers up to the given N. The use of mutableSetOf allows for efficient management of perfect squares, reducing the complexity of the search.

Code Execution and Results

Now let’s test the code we have written and check the results. For example, if we set N to 20 and call the function, we can obtain the following result:

fun main() {
    val n = 20
    val result = findNonPerfectSquares(n)
    println("Non-perfect squares from 1 to $n: $result")
}

When we print the result using the above main function, we get the following:

Non-perfect squares from 1 to 20: [2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20]

Complexity Analysis

Looking at the time complexity of this problem:

  • For loop to calculate perfect squares: O(√N)
  • Checking perfect squares in the loop up to N: O(N)

Thus, the overall time complexity is O(√N + N) = O(N).

Conclusion

In this course, we covered an algorithm problem of finding non-perfect squares. We learned the structure of the problem and how to implement it in Kotlin, as well as the concept of perfect squares and how to manage data efficiently. Since this is a type of problem commonly encountered in coding tests, it is important to approach it as if you are solving a real problem. If you have any questions or additional topics you want to know about, please leave a comment! We look forward to more informative algorithm courses!