LeetCode 3233 - Find the Count of Numbers Which Are Not Special

The problem asks us to count how many integers in the inclusive range [l, r] are not special. A number is considered special if it has exactly two proper divisors. A proper divisor of a number x is any positive divisor of x other than x itself.

leetcodemediumarraymathnumber-theory

LeetCode Problem 3233

Difficulty: 🟡 Medium
Topics: Array, Math, Number Theory

Solution

Problem Understanding

The problem asks us to count how many integers in the inclusive range [l, r] are not special.

A number is considered special if it has exactly two proper divisors.

A proper divisor of a number x is any positive divisor of x other than x itself. For example:

  • Proper divisors of 4 are 1 and 2
  • Proper divisors of 6 are 1, 2, and 3

So:

  • 4 is special because it has exactly two proper divisors
  • 6 is not special because it has three proper divisors

The input consists of two integers:

  • l, the left boundary of the range
  • r, the right boundary of the range

The output should be the number of integers between l and r inclusive that are not special.

The key challenge comes from the constraints:

  • 1 <= l <= r <= 10^9

Since the upper bound can be as large as one billion, we cannot iterate through every number and compute all divisors directly using brute force divisor enumeration. We need a mathematical observation that characterizes special numbers efficiently.

Several edge cases are important:

  • The range may contain very small numbers like 1 or 2
  • The range may contain no special numbers at all
  • The range may contain exactly one special number
  • The range may be extremely large, requiring an efficient mathematical solution
  • Perfect squares need careful handling because divisor counts behave differently for squares

Approaches

Brute Force Approach

A straightforward solution is to iterate through every number in the range [l, r] and count how many proper divisors it has.

For each number x:

  1. Check every integer from 1 to x - 1
  2. Count how many values divide x
  3. If the count equals 2, mark the number as special
  4. Otherwise count it as non-special

This approach is correct because it directly follows the problem definition.

However, it is far too slow. In the worst case:

  • The range size can approach 10^9
  • Divisor checking for each number can take up to O(x)

This leads to an enormous runtime.

Even optimizing divisor counting to O(sqrt(x)) is still too slow for large ranges.

Key Insight

A number has exactly two proper divisors if and only if it is the square of a prime number.

Let us understand why.

Suppose x = p^2, where p is prime.

The divisors of p^2 are:

  • 1
  • p
  • p^2

The proper divisors are:

  • 1
  • p

Exactly two proper divisors exist.

Now consider any number that is not a prime square:

  • If it is prime, it only has one proper divisor: 1
  • If it has more composite structure, it will have more than two proper divisors
  • If it is not a perfect square, divisors usually come in pairs, increasing the count

Therefore:

Special numbers are exactly the squares of prime numbers.

This transforms the problem into:

  1. Count how many prime numbers p satisfy:

l <= p^2 <= r 2. Subtract that count from the total number of integers in the range

Since:

p^2 <= 10^9

we only need primes up to:

$\sqrt{10^9} \approx 31623$

This is small enough for the Sieve of Eratosthenes.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((r - l + 1) × √r) O(1) Checks divisors for every number
Optimal O(√r log log √r) O(√r) Uses prime squares observation and sieve

Algorithm Walkthrough

Optimal Algorithm

  1. Compute the total number of integers in the range.

The range [l, r] contains:

$r - l + 1$

numbers. 2. Compute the maximum possible prime we need to consider.

Since special numbers are prime squares, we only need primes p such that:

$p^2 \le r$

Therefore:

$p \le \lfloor \sqrt{r} \rfloor$ 3. Generate all primes up to sqrt(r) using the Sieve of Eratosthenes.

The sieve works by:

  • Initially assuming every number is prime
  • Starting from 2
  • Marking all multiples of each prime as composite

This efficiently generates all primes in near-linear time. 4. For every prime p, compute p * p.

If:

$l \le p^2 \le r$

then p^2 is a special number. 5. Count how many special numbers exist. 6. Return:

$(r - l + 1) - \text{specialCount}$

because the problem asks for non-special numbers.

Why it works

The algorithm relies on the mathematical fact that a number has exactly two proper divisors if and only if it is the square of a prime number.

Every prime square has divisors {1, p, p²}, giving exactly two proper divisors. Any other number either has fewer proper divisors or more than two. Therefore counting prime squares in the range exactly counts the special numbers, and subtracting from the total gives the correct answer.

Python Solution

class Solution:
    def nonSpecialCount(self, l: int, r: int) -> int:
        import math

        limit = int(math.isqrt(r))

        is_prime = [True] * (limit + 1)
        is_prime[0] = False

        if limit >= 1:
            is_prime[1] = False

        for num in range(2, int(math.isqrt(limit)) + 1):
            if is_prime[num]:
                for multiple in range(num * num, limit + 1, num):
                    is_prime[multiple] = False

        special_count = 0

        for prime in range(2, limit + 1):
            if is_prime[prime]:
                square = prime * prime

                if l <= square <= r:
                    special_count += 1

        total_numbers = r - l + 1

        return total_numbers - special_count

The implementation begins by computing sqrt(r) because no prime larger than this can produce a square within the range.

The sieve array is_prime stores whether each number is prime. Initially all values are assumed to be prime except 0 and 1.

The nested loop marks multiples of each discovered prime as composite. Starting from num * num is an important optimization because smaller multiples would already have been processed by smaller primes.

After generating primes, the code iterates through all prime numbers and computes their squares. Whenever a square lies inside [l, r], it contributes to the count of special numbers.

Finally, the number of special numbers is subtracted from the total size of the range.

Go Solution

package main

import "math"

func nonSpecialCount(l int, r int) int {
	limit := int(math.Sqrt(float64(r)))

	isPrime := make([]bool, limit+1)

	for i := range isPrime {
		isPrime[i] = true
	}

	if limit >= 0 {
		isPrime[0] = false
	}

	if limit >= 1 {
		isPrime[1] = false
	}

	for num := 2; num*num <= limit; num++ {
		if isPrime[num] {
			for multiple := num * num; multiple <= limit; multiple += num {
				isPrime[multiple] = false
			}
		}
	}

	specialCount := 0

	for prime := 2; prime <= limit; prime++ {
		if isPrime[prime] {
			square := prime * prime

			if square >= l && square <= r {
				specialCount++
			}
		}
	}

	totalNumbers := r - l + 1

	return totalNumbers - specialCount
}

The Go implementation follows the same logic as the Python version.

One difference is that Go does not provide an integer square root function equivalent to Python's math.isqrt, so we use math.Sqrt and convert the result to int.

Slices are used for the sieve array. Since Go initializes boolean slices to false, we explicitly set all values to true before running the sieve.

Integer overflow is not a concern here because:

$31623^2 < 2^{31}$

so all computations safely fit inside standard integer ranges.

Worked Examples

Example 1

Input:

l = 5
r = 7

Step 1: Compute limit

$\lfloor \sqrt{7} \rfloor = 2$

We only need primes up to 2.

Step 2: Generate primes

Number Prime?
0 No
1 No
2 Yes

Step 3: Check prime squares

Prime Square In Range [5,7]?
2 4 No

No special numbers exist.

Step 4: Compute result

Value Result
Total numbers 3
Special numbers 0
Non-special numbers 3

Answer:

3

Example 2

Input:

l = 4
r = 16

Step 1: Compute limit

$\lfloor \sqrt{16} \rfloor = 4$

Step 2: Generate primes

Number Prime?
2 Yes
3 Yes
4 No

Step 3: Check prime squares

Prime Square In Range [4,16]?
2 4 Yes
3 9 Yes

Special numbers are:

4, 9

Step 4: Compute result

Value Result
Total numbers 13
Special numbers 2
Non-special numbers 11

Answer:

11

Complexity Analysis

Measure Complexity Explanation
Time O(√r log log √r) Sieve of Eratosthenes up to √r
Space O(√r) Boolean sieve array

The dominant cost comes from generating primes with the sieve. The Sieve of Eratosthenes runs in:

$O(n \log \log n)$

where:

$n = \sqrt{r}$

Since √10^9 ≈ 31623, the algorithm is extremely efficient for the given constraints.

Test Cases

sol = Solution()

assert sol.nonSpecialCount(5, 7) == 3      # no special numbers
assert sol.nonSpecialCount(4, 16) == 11    # 4 and 9 are special
assert sol.nonSpecialCount(1, 1) == 1      # smallest range
assert sol.nonSpecialCount(4, 4) == 0      # single special number
assert sol.nonSpecialCount(9, 9) == 0      # another single special number
assert sol.nonSpecialCount(8, 8) == 1      # non-special composite
assert sol.nonSpecialCount(2, 3) == 2      # only primes, no special numbers
assert sol.nonSpecialCount(1, 10) == 8     # special numbers are 4 and 9
assert sol.nonSpecialCount(15, 25) == 10   # only 25 is special
assert sol.nonSpecialCount(16, 16) == 1    # perfect square but not prime square
assert sol.nonSpecialCount(1, 100) == 96   # special numbers are 4, 9, 25, 49
Test Why
[5,7] Verifies range with no special numbers
[4,16] Verifies multiple special numbers
[1,1] Smallest valid input
[4,4] Single-element range containing a special number
[9,9] Another prime square edge case
[8,8] Composite but non-special number
[2,3] Prime numbers are not special
[1,10] Mixed small range
[15,25] Range ending with a special number
[16,16] Perfect square that is not a prime square
[1,100] Larger validation case

Edge Cases

Range Contains Only One Number

A single-element range like [4,4] or [8,8] can expose off-by-one errors.

The implementation handles this correctly because the total number count is computed as:

$r - l + 1$

which correctly gives 1 for single-element ranges.

Perfect Squares That Are Not Prime Squares

Numbers like 16 or 36 are perfect squares, but they are not special because:

  • 16 = 4²
  • 36 = 6²

and 4 and 6 are not prime.

These numbers have more than two proper divisors. The implementation avoids incorrectly counting them because it only considers squares of numbers identified as prime by the sieve.

Very Large Upper Bound

The constraint:

$r \le 10^9$

makes brute force approaches infeasible.

The optimized solution remains fast because it only computes primes up to:

$\sqrt{10^9} \approx 31623$

which is small enough for efficient sieve processing.

Small Numbers Like 1 and 2

Numbers 1 and 2 have fewer than two proper divisors:

  • 1 has no proper divisors
  • 2 has only one proper divisor, 1

The implementation naturally excludes them because neither is a square of a prime number.