Skip to main content
Talentd

Find the Count of Numbers Which Are Not Special - Solution & Explanation

MediumArrayMathNumber Theory12 min readAsked at: Microsoft
Practice this problem

Problem Statement

You are given 2 positive integers l and r. For any number x, all positive divisors of x except x are called the proper divisors of x.

A number is called special if it has exactly 2 proper divisors. For example:

  • The number 4 is special because it has proper divisors 1 and 2.
  • The number 6 is not special because it has proper divisors 1, 2, and 3.

Return the count of numbers in the range [l, r] that are not special.

 

Example 1:

Input: l = 5, r = 7

Output: 3

Explanation:

There are no special numbers in the range [5, 7].

Example 2:

Input: l = 4, r = 16

Output: 11

Explanation:

The special numbers in the range [4, 16] are 4 and 9.

 

Constraints:

  • 1 <= l <= r <= 109

Approach Overview

Problem Overview: Given two integers l and r, count how many numbers in this range are not special. A number is special if it has exactly two proper divisors. That property only holds for numbers that are the square of a prime (for example, 4 = 2², 9 = 3²). The task reduces to counting how many prime squares exist in the range and subtracting them from the total numbers.

Approach 1: Brute Force with Optimization (O(n * sqrt(n)) time, O(1) space)

Iterate through every number in the range [l, r]. For each value, count its divisors by checking integers up to sqrt(num). Track how many proper divisors appear. If exactly two proper divisors exist, the number is special. Otherwise it contributes to the answer. This approach directly follows the definition and works for small ranges, but the repeated divisor checks make it slow when r - l is large.

Approach 2: Prime Square Detection (O(sqrt(r)) time, O(1) space)

The key observation from number theory is that only numbers of the form p² where p is prime have exactly two proper divisors. Instead of checking every number, compute integers p such that p² lies inside the range. For each candidate p, run a primality check up to sqrt(p). Every prime found represents one special number. The final answer is (r - l + 1) - countPrimeSquares. This removes the need to examine every number in the interval.

Approach 3: Check for Squares of Primes (O(sqrt(r) * log log r) time, O(sqrt(r)) space)

Instead of repeated primality tests, generate all primes up to sqrt(r) using the Sieve of Eratosthenes. For each prime p, compute p * p and check whether it falls within the interval. This converts many expensive primality checks into a single preprocessing step. The approach relies heavily on mathematical structure and is common in problems involving math and divisor properties.

Approach 4: Mathematical Pattern Recognition for Efficiency (O(sqrt(r)) time, O(sqrt(r)) space)

Recognize that the count of special numbers equals the count of primes p where p² lies in the range. Compute low = ceil(sqrt(l)) and high = floor(sqrt(r)). Then count primes in the interval [low, high] using a sieve or fast prime check. This reframes the task as a prime-counting problem rather than scanning the entire numeric range. It is the cleanest formulation and scales well for large bounds.

Recommended for interviews: Interviewers usually expect the prime-square observation. Start by explaining the brute force divisor check to show you understand the definition, then pivot to the number theory insight that only squares of primes qualify. Implementing a prime check or sieve over sqrt(r) demonstrates strong problem reduction skills and familiarity with array-based sieve techniques.

Approach 1: Prime Square Detection

In this approach, we detect numbers that are perfect squares of prime numbers. These correspond to numbers with exactly 2 proper divisors, which are special numbers. For a number n to be special, it should be p^2 where p is a prime.

By identifying these numbers using a sieve method up to the square root of r, we can count the numbers in the range that are special and compute the non-special count.

This Python solution first computes the sieve of Eratosthenes to find all prime numbers up to the square root of r. It then counts all perfect squares of these primes that lie within the specified range [l, r]. The count is used to determine the number of non-special numbers in the given range.

Code

Python

Python

Complexity

Time Complexity: O(√r log log √r + n), where n is the number of elements in the range.
Space Complexity: O(√r) for the sieve.

Try this approach in the editor →

Approach 2: Brute Force with Optimization

This approach involves checking each number within the range [l, r] to determine if it is special by counting its proper divisors. However, to optimize, we only check up to the square root of the number for its divisors, reducing unnecessary checks.

This Java solution iterates through each number in the range [l, r] and uses an optimized divisor count method which only considers divisors up to the square root of the number. It counts the number of proper divisors and determines whether the number is special based on having exactly 2 proper divisors.

Code

Java

Java

Complexity

Time Complexity: O(n√d), where n is the range length and d is the average number checked (usually ≤ √r).
Space Complexity: O(1), constant space.

Try this approach in the editor →

Approach 3: Check for Squares of Primes

The numbers that have exactly 2 proper divisors are the squares of prime numbers. For example, 4 = 2^2 and 9 = 3^2, both have proper divisors 1 and the prime number itself. Therefore, to solve the problem, you can find all squares of prime numbers in the range [l, r], and count the numbers in this range that are not the square of a prime number.

This implementation checks for all prime numbers up to the square root of r. For each prime, it computes the square and checks if it lies in the range [l, r]. The numbers that are not special are those which are not prime squares within this range.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(√r log log r) due to the sieve approach for finding primes, then iterating up to √r for checking primes.
Space Complexity: O(√r) for storing prime numbers and their squares.

Try this approach in the editor →

Approach 4: Mathematical Pattern Recognition for Efficiency

Instead of computing which numbers are special, recognize that special numbers up to √r form a limited sequence of squares of all primes ≤ √r. Calculate non-special numbers in the range by identifying these special numbers.

The solution finds squares of all primes ≤ √r and checks if they lie within the range [l, r]. The numbers that do not match these considerable squares are counted as not special.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(√r log log r) due to iterating over potential primes up to √r.
Space Complexity: O(1) if we consider the set of prime squares small due to limited elements.

Try this approach in the editor →

Approach 5: Mathematics

According to the problem description, we can observe that only the squares of prime numbers are special numbers. Therefore, we can first preprocess all prime numbers less than or equal to \sqrt{10^9}, and then iterate through the interval [\lceil\sqrt{l}\rceil, \lfloor\sqrt{r}\rfloor], counting the number of primes cnt in the interval. Finally, we return r - l + 1 - cnt.

The time complexity is O(\sqrt{m}), and the space complexity is O(\sqrt{m}), where m = 10^9.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prime Square Detection

Time Complexity: O(√r log log √r + n), where n is the number of elements in the range.
Space Complexity: O(√r) for the sieve.

Brute Force with Optimization

Time Complexity: O(n√d), where n is the range length and d is the average number checked (usually ≤ √r).
Space Complexity: O(1), constant space.

Check for Squares of Primes

Time Complexity: O(√r log log r) due to the sieve approach for finding primes, then iterating up to √r for checking primes.
Space Complexity: O(√r) for storing prime numbers and their squares.

Mathematical Pattern Recognition for Efficiency

Time Complexity: O(√r log log r) due to iterating over potential primes up to √r.
Space Complexity: O(1) if we consider the set of prime squares small due to limited elements.

Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Divisor CountingO(n * sqrt(n))O(1)Small ranges or when demonstrating the definition of special numbers
Prime Square DetectionO(sqrt(r))O(1)General optimized approach using prime checks
Squares of Primes with SieveO(sqrt(r) log log r)O(sqrt(r))When many prime checks are required and preprocessing helps
Prime Counting via Square RootsO(sqrt(r))O(sqrt(r))Best mathematical formulation for large ranges

Video Solution

3233. Find the Count of Numbers Which Are Not Special (Leetcode Medium) • Programming Live with Larry • 748 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Find the Count of Numbers Which Are Not Special easy or hard?
The problem is rated Medium because the brute force interpretation looks expensive, but the correct solution relies on recognizing a number theory pattern. Once you realize special numbers must be squares of primes, the implementation becomes straightforward.
Find the Count of Numbers Which Are Not Special Python/Java solution
In Python, iterate p from 2 to sqrt(r) and check if p is prime, counting cases where p*p lies within [l, r]. In Java or C++, the same idea is often implemented with a sieve array to generate primes efficiently before checking their squares.
How to solve Find the Count of Numbers Which Are Not Special in O(sqrt(n))?
Compute the square root bounds of the range: low = ceil(sqrt(l)) and high = floor(sqrt(r)). Every integer p in this range whose value is prime contributes one special number because p^2 lies inside the range. Count those primes and subtract the result from the total number of integers in the interval.
What is the best approach for Find the Count of Numbers Which Are Not Special?
The optimal approach is to recognize that special numbers are exactly the squares of prime numbers. Instead of scanning every number in the range, compute primes up to sqrt(r) and check which of their squares fall inside [l, r]. This reduces the problem to counting prime squares and subtracting them from the total range size.
Is Find the Count of Numbers Which Are Not Special asked at Google/Amazon/Meta?
Problems involving prime detection, divisor counting, and mathematical reduction frequently appear in interviews at companies like Amazon, Google, and fintech startups. This specific pattern—reducing a divisor condition to prime squares—is a common number theory trick used in coding interviews.
What data structure is used in Find the Count of Numbers Which Are Not Special?
Most optimized implementations use an array-based Sieve of Eratosthenes to precompute primes up to sqrt(r). Aside from that, the solution mainly relies on mathematical reasoning rather than complex data structures.
What is the time complexity of Find the Count of Numbers Which Are Not Special?
The optimized solution runs in O(sqrt(r)) time if you perform primality checks for numbers up to sqrt(r). Using the Sieve of Eratosthenes changes the complexity to O(sqrt(r) log log r) with O(sqrt(r)) space, which is still efficient for large ranges.

Ready to solve this problem?

Practice Find the Count of Numbers Which Are Not Special with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Primes