C# Coding Test Course, Finding Numbers That Are Not Perfect Squares

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

  1. HashSet squareNumbers: A HashSet to store square numbers. HashSet is used for fast lookup.
  2. for (int i = 1; i * i <= N; i++): Starts from 1 to generate square numbers.
  3. squareNumbers.Add(i * i): Adds the generated square number to the HashSet.
  4. nonSquareCount = N - squareNumbers.Count: Subtracts the count of square numbers from N to get the count of non-square numbers.
  5. 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.