python coding test course, finding non-squares

Hello, everyone! In this blog post, we will solve an algorithm problem called Finding Non-Square Numbers. This problem is one of the types that frequently appear in coding tests, requiring both mathematical thinking and programming skills. In this article, we will explain the problem description, solution ideas, actual code, and time complexity analysis in detail.

Problem Description

Given a natural number N, write a function to count the number of natural numbers that are not perfect squares among the natural numbers from 1 to N. A perfect square is a number that can be expressed in the form x * x = y for some natural number x. For example, 1 (1 * 1), 4 (2 * 2), 9 (3 * 3), and 16 (4 * 4) are perfect squares.

Input

  • A natural number N (1 ≤ N ≤ 106)

Output

  • Print the count of numbers that are not perfect squares.

Example

Input

N = 10

Output

7

Explanation: The natural numbers from 1 to 10 are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Among these, 1, 4, and 9 are perfect squares, so there are 10 – 3 = 7 numbers that are not perfect squares.

Solution Idea

To solve this problem, we must follow these steps:

  1. Check whether each natural number from 1 to N is a perfect square.
  2. Count the number of perfect squares and subtract this from N to get the count of non-square numbers.

To find perfect squares, we can square integers from 1 to √N and precompute the perfect squares from 1 to N, then count the number of perfect squares and subtract this from N. This allows us to solve the problem with a time complexity of O(√N).

Implementation

Now, let’s write the code to solve the problem in Python. Below is a function that counts the number of non-square numbers:


import math

def count_non_squares(N):
    if N < 1:
        return 0
    
    # Calculate the number of perfect squares
    square_count = int(math.sqrt(N))
    
    # Count of non-perfect square numbers
    return N - square_count

Code Explanation

  • First, we use math.sqrt(N) to calculate the square root of N. This provides basic information to know how many perfect squares are there among the natural numbers less than or equal to N.
  • Next, we use int() to convert the square root to an integer, representing the count of perfect squares.
  • Finally, we subtract the count of perfect squares from N to print the count of non-perfect square numbers.

Time Complexity Analysis

The time complexity of this problem is O(1). Even when N is large, calculating the square root can be done quickly. Therefore, this algorithm is very efficient.

Conclusion

In this post, we covered the problem of finding non-square numbers. This problem requires simple mathematical thinking and can help cultivate efficient algorithm coding skills for problem-solving. Since it is a type of problem frequently encountered in coding tests, be sure to practice well!

In the next lecture, we will tackle more interesting problems. Thank you!