Finding Non-Square Numbers
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.
Problem Description
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.
Input
- An integer N (1 ≤ N ≤ 10^6)
Output
- Print the count of non-square numbers
Example
Input Example: 10 Output Example: 8
Approach to Solve the Problem
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:
- X is an integer, and Y = X * X
To find square numbers from 1 to N, we need the following logic.
1. Create a List of Square Numbers
Calculating square numbers for numbers from 1 to N has a complexity of O(√N), so we pre-calculate the square numbers and store them in a list.
2. Compare with Integer N
Next, count how many numbers from 1 to N are included in the list of square numbers.
3. Derive the Final Result
Subtracting the count of square numbers from N gives the count of non-square numbers. This process has a time complexity of O(N).
Code Implementation
Now, based on the above logic, let’s write the code in C#.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int N = int.Parse(Console.ReadLine());
HashSet squareNumbers = new HashSet();
// Add square numbers to the HashSet
for (int i = 1; i * i <= N; i++)
{
squareNumbers.Add(i * i);
}
int nonSquareCount = N - squareNumbers.Count; // Count of non-square numbers
Console.WriteLine(nonSquareCount);
}
}
Code Explanation
HashSet
: A HashSet to store square numbers. HashSet is used for fast lookup.squareNumbers for (int i = 1; i * i <= N; i++)
: Starts from 1 to generate square numbers.squareNumbers.Add(i * i)
: Adds the generated square number to the HashSet.nonSquareCount = N - squareNumbers.Count
: Subtracts the count of square numbers from N to get the count of non-square numbers.Console.WriteLine(nonSquareCount)
: Prints the final result.
Complexity Analysis
Analyzing the time complexity of this algorithm:
- Generating square numbers: O(√N) (up to √N square numbers generated)
- Counting non-square numbers: O(1) (constant time as it retrieves the size of the HashSet)
Therefore, the overall time complexity is O(√N). This algorithm operates very efficiently within the given constraints.
Conclusion
In this tutorial, we explored how to solve the algorithm problem of finding non-square numbers. We hope to enhance problem-solving skills through the thought process behind solving the problem. Continuous practice with various algorithm problems is essential in the future.