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.<\/p>\n<\/div>\n
The problem is as follows:<\/p>\n
\nFinding Non-Perfect Squares<\/strong>
\n Write a function to find all numbers that are not perfect squares among natural numbers from 1 to N. <\/p>\nInput<\/strong>: Integer N (1 \u2264 N \u2264 1000)
\nOutput<\/strong>: List of non-perfect square numbers\n <\/p><\/blockquote>\n<\/div>\n\nProblem Analysis<\/h2>\n
To solve this problem, the following steps are necessary:<\/p>\n
\n
- Iterate through all natural numbers from 1 to N.<\/li>\n
- Devise a method to check if each number is a perfect square.<\/li>\n
- Store the numbers that are not perfect squares in a list.<\/li>\n<\/ul>\n
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 \u221aN, 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.<\/p>\n<\/div>\n
\nAlgorithm Design<\/h2>\n
Based on the above process, the following algorithm can be designed:<\/p>\n
\n
- Create an empty list.<\/li>\n
- Run a loop from 1 to N.<\/li>\n
- Determine whether each number is a perfect square.<\/li>\n
- If it is not a perfect square, add it to the list.<\/li>\n
- Output the result list.<\/li>\n<\/ol>\n<\/div>\n
\nKotlin Code Implementation<\/h2>\n
Now, let\u2019s implement this algorithm in Kotlin:<\/p>\n
fun findNonPerfectSquares(n: Int): List{\n val nonPerfectSquares = mutableListOf ()\n \n \/\/ Set to store perfect squares\n val perfectSquares = mutableSetOf ()\n \n \/\/ Calculate perfect squares from 1 to n\n for (i in 1..Math.sqrt(n.toDouble()).toInt()) {\n perfectSquares.add(i * i)\n }\n \n \/\/ Explore from 1 to N\n for (i in 1..n) {\n \/\/ Add to the list if it is not a perfect square\n if (i !in perfectSquares) {\n nonPerfectSquares.add(i)\n }\n }\n \n return nonPerfectSquares\n}<\/Int><\/Int><\/Int><\/code><\/pre>\n In the above code, the
findNonPerfectSquares<\/code> function returns a list of numbers that are not perfect squares among natural numbers up to the given N. The use ofmutableSetOf<\/code> allows for efficient management of perfect squares, reducing the complexity of the search.<\/p>\n<\/div>\n\nCode Execution and Results<\/h2>\n
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:<\/p>\n
fun main() {\n val n = 20\n val result = findNonPerfectSquares(n)\n println(\"Non-perfect squares from 1 to $n: $result\")\n}<\/code><\/pre>\nWhen we print the result using the above
main<\/code> function, we get the following:<\/p>\nNon-perfect squares from 1 to 20: [2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20]<\/code><\/pre>\n<\/div>\n