In this tutorial, we will cover an algorithm problem of finding non-square numbers. The goal is to learn various approaches to solve the problem and enhance problem-solving skills for coding tests.<\/p>\n
Given an integer N, the task is to count the number of non-square numbers among the integers from 1 to N. For example, if N is 10, the square numbers are 1, 4, and 9, making the non-square numbers 1, 2, 3, 5, 6, 7, 8, and 10, which totals to 8.<\/p>\n
\n Input Example:\n 10\n\n Output Example:\n 8\n <\/pre>\nApproach to Solve the Problem<\/h3>\n
There can be various methods to solve this problem. However, to find the optimal method, we need to generate square numbers and infer the count of non-square numbers based on that. A square number is defined as follows:<\/p>\n
To find square numbers from 1 to N, we need the following logic.<\/p>\n
Calculating square numbers for numbers from 1 to N has a complexity of O(\u221aN), so we pre-calculate the square numbers and store them in a list.<\/p>\n
Next, count how many numbers from 1 to N are included in the list of square numbers.<\/p>\n
Subtracting the count of square numbers from N gives the count of non-square numbers. This process has a time complexity of O(N).<\/p>\n
Now, based on the above logic, let\u2019s write the code in C#.<\/p>\n
\nusing System;\nusing System.Collections.Generic;\n\nclass Program\n{\n static void Main()\n {\n int N = int.Parse(Console.ReadLine());\n HashSet squareNumbers = new HashSet();\n\n \/\/ Add square numbers to the HashSet\n for (int i = 1; i * i <= N; i++)\n {\n squareNumbers.Add(i * i);\n }\n\n int nonSquareCount = N - squareNumbers.Count; \/\/ Count of non-square numbers\n\n Console.WriteLine(nonSquareCount);\n }\n}\n <\/int><\/int><\/code><\/pre>\nCode Explanation<\/h3>\n\nHashSet squareNumbers<\/int><\/code>: A HashSet to store square numbers. HashSet is used for fast lookup.<\/li>\nfor (int i = 1; i * i <= N; i++)<\/code>: Starts from 1 to generate square numbers.<\/li>\nsquareNumbers.Add(i * i)<\/code>: Adds the generated square number to the HashSet.<\/li>\nnonSquareCount = N - squareNumbers.Count<\/code>: Subtracts the count of square numbers from N to get the count of non-square numbers.<\/li>\nConsole.WriteLine(nonSquareCount)<\/code>: Prints the final result.<\/li>\n<\/ol>\nComplexity Analysis<\/h3>\n
Analyzing the time complexity of this algorithm:<\/p>\n