#3233
Find the Count of Numbers Which Are Not Special
MediumArrayMathNumber TheorySieve of EratosthenesMathematical properties of numbers
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n log log n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n log log n)Space O(n)
A special number is defined as the square of a prime number. Thus, we can find all prime numbers in the range [sqrt(l), sqrt(r)] and count their squares within the range [l, r]. This approach is efficient because it reduces the problem to finding primes and their squares.
⚙️
Algorithm
4 steps- 1Step 1: Calculate the lower and upper bounds for prime numbers as sqrt(l) and sqrt(r).
- 2Step 2: Use the Sieve of Eratosthenes to find all prime numbers up to sqrt(r).
- 3Step 3: For each prime, calculate its square and check if it lies within the range [l, r].
- 4Step 4: Count the number of special numbers (squares of primes) and subtract from the total count of numbers in the range.
solution.py26 lines
1# Full working Python code
2import math
3
4def count_not_special(l, r):
5 def sieve(n):
6 is_prime = [True] * (n + 1)
7 p = 2
8 while (p * p <= n):
9 if (is_prime[p]):
10 for i in range(p * p, n + 1, p):
11 is_prime[i] = False
12 p += 1
13 return [p for p in range(2, n + 1) if is_prime[p]]
14
15 lower = math.isqrt(l)
16 upper = math.isqrt(r)
17 primes = sieve(upper)
18 special_count = 0
19
20 for prime in primes:
21 square = prime * prime
22 if square >= l and square <= r:
23 special_count += 1
24
25 total_count = r - l + 1
26 return total_count - special_countℹ
Complexity note: The time complexity is O(n log log n) due to the Sieve of Eratosthenes for finding primes, which is efficient for our range. The space complexity is O(n) for storing the prime numbers.
- 1A special number is defined as the square of a prime number.
- 2Using the Sieve of Eratosthenes allows us to efficiently find primes in a given range.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.