Find the Count of Numbers Which Are Not Special
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly implements the definition from the problem description. We iterate through every number x in the given range [l, r]. For each number, we find all its proper divisors and count them. If the count is exactly 2, we classify the number as special. Finally, we subtract the count of special numbers from the total number of elements in the range to get the result.
Algorithm
- The total number of integers in the range
[l, r]isr - l + 1. - We can find the number of non-special numbers by calculating
(total numbers) - (special numbers). - To find the count of special numbers:
- Initialize a counter
specialCountto 0. - Loop through each integer
xfromltor. - For each
x, find the number of its proper divisors.- Initialize a
divisorCountto 0. - Loop with a variable
ifrom 1 tox - 1. - If
xis divisible byi(x % i == 0), incrementdivisorCount.
- Initialize a
- If
divisorCountis exactly 2, it meansxis a special number. IncrementspecialCount. - After checking all numbers from
ltor, the final answer is(r - l + 1) - specialCount.
- Initialize a counter
Walkthrough
The core idea is to check each number individually based on the definition of a special number. A number is special if it has exactly two proper divisors. The algorithm iterates from l to r, and for each number, it performs another iteration from 1 up to the number itself to count its proper divisors. If the count of proper divisors is two, the number is counted as special. The total count of non-special numbers is then the size of the range minus the count of special numbers found.
class Solution { public int nonSpecialCount(int l, int r) { int specialCount = 0; for (int x = l; x <= r; x++) { if (isSpecial(x)) { specialCount++; } } return (r - l + 1) - specialCount; } private boolean isSpecial(int n) { if (n <= 3) { // Numbers 1, 2, 3 have less than 2 proper divisors return false; } int properDivisorCount = 0; // A simple optimization is to loop up to n/2 for (int i = 1; i <= n / 2; i++) { if (n % i == 0) { properDivisorCount++; } } return properDivisorCount == 2; }}Complexity
Time
O((r - l) * r). The outer loop runs `r - l + 1` times. The inner `isSpecial` function takes O(n) time for each number `n`. In the worst case, this is `O((r - l) * r)`. This is too slow for the given constraints.
Space
O(1), as we only use a few variables to store counts, requiring constant extra space.
Trade-offs
Pros
Simple to understand and implement directly from the problem definition.
Cons
Extremely inefficient due to its high time complexity.
Will result in a Time Limit Exceeded (TLE) error for the given constraints.
This approach improves upon the brute-force method by using a key mathematical property of special numbers. A number is special if and only if it is the square of a prime number. Instead of counting all proper divisors, for each number x in the range [l, r], we first check if it's a perfect square. If it is, we then check if its square root is a prime number. This check is significantly faster than counting all divisors.
Algorithm
- First, we deduce the mathematical property of special numbers. A number
xis special if it has 2 proper divisors, meaning it has 3 total divisors. A number has an odd number of divisors if and only if it is a perfect square. For the number of divisors to be exactly 3 (a prime number), the number must be of the formp^2, wherepis a prime number. - The algorithm is as follows:
- Initialize
specialCountto 0. - Iterate through each number
xfromltor. - For each
x, check if it's a special number: a. Calculate the integer square root,s = (int) Math.sqrt(x). b. Ifs * s == x(i.e.,xis a perfect square), proceed to check ifsis prime. c. To check ifsis prime, use a helper functionisPrime(s)that checks for divisibility from 2 up tosqrt(s). d. Ifxis a perfect square and its rootsis prime, incrementspecialCount. - The final result is
(r - l + 1) - specialCount.
- Initialize
Walkthrough
By understanding that special numbers are squares of primes, we can optimize the check. The algorithm iterates through each number x from l to r. For each x, it calculates s = sqrt(x). If x is not a perfect square (i.e., s*s != x), it cannot be special. If it is a perfect square, we then need to verify if the root s is a prime number. A standard primality test for s involves checking for divisors up to sqrt(s). This avoids the slow process of counting all divisors for x.
class Solution { public int nonSpecialCount(int l, int r) { int specialCount = 0; for (int x = l; x <= r; x++) { if (isSpecial(x)) { specialCount++; } } return (r - l + 1) - specialCount; } private boolean isPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } private boolean isSpecial(int n) { if (n <= 3) return false; int s = (int) Math.sqrt(n); if (s * s != n) { return false; } return isPrime(s); }}Complexity
Time
O((r - l) * r^(1/4)). The outer loop runs `r - l + 1` times. For each number `x`, the primality test on its square root `s` takes `O(sqrt(s)) = O(sqrt(sqrt(x))) = O(x^(1/4))` time. This is still too slow if the range `r - l` is large.
Space
O(1). No significant extra space is used besides a few variables for calculation.
Trade-offs
Pros
More efficient than the first approach by using a mathematical insight.
Correctly identifies the structure of special numbers.
Cons
Still inefficient for large ranges where
r - lis large.Will likely result in a Time Limit Exceeded (TLE) error if the range is not small.
This is the most efficient approach. Instead of checking every number in the potentially vast range [l, r], we generate all the special numbers and count how many fall within the range. Since special numbers are squares of primes (p^2), we only need to find primes p such that p^2 <= r. The most effective way to find all primes up to a certain limit (here, sqrt(r)) is the Sieve of Eratosthenes. After finding the primes, we square them and check if they are in [l, r].
Algorithm
- The key insight is to generate the special numbers themselves, rather than testing each number in the
[l, r]range. - A number
xis special ifx = p^2for some primep. - We need to find primes
psuch thatl <= p^2 <= r. The maximum prime we need to consider isp <= sqrt(r). - The algorithm is as follows:
- Calculate the upper bound for our prime search:
limit = (int) Math.sqrt(r). - Use the Sieve of Eratosthenes to generate all prime numbers up to
limit. a. Create a boolean arrayisPrimeof sizelimit + 1and initialize all entries totrue. b. MarkisPrime[0]andisPrime[1]asfalse. c. Iterate fromp = 2up tosqrt(limit). IfisPrime[p]istrue, then iterate through its multiplesj = p * ptolimitand markisPrime[j]asfalse. - Initialize
specialCount = 0. - Iterate from
p = 2up tolimit. - If
isPrime[p]istrue, calculate its square:specialNum = (long) p * p. - Check if this special number falls within our range:
if (specialNum >= l && specialNum <= r). - If it does, increment
specialCount. - The final answer is
(r - l + 1) - specialCount.
- Calculate the upper bound for our prime search:
Walkthrough
The optimal strategy is to change the perspective: instead of checking numbers, we generate the numbers that fit the criteria. We need to count p^2 where p is prime and l <= p^2 <= r. This means we only need to find primes up to sqrt(r). Since r <= 10^9, sqrt(r) is at most 31622, which is a small number.
We can use the Sieve of Eratosthenes to pre-compute all primes up to sqrt(r). Once we have the list of primes, we iterate through them, square each prime, and check if the result is within the [l, r] interval. This avoids iterating over the large [l, r] range entirely.
import java.util.Arrays; class Solution { public int nonSpecialCount(int l, int r) { int limit = (int) Math.sqrt(r); boolean[] isPrime = new boolean[limit + 1]; Arrays.fill(isPrime, true); if (limit >= 0) isPrime[0] = false; if (limit >= 1) isPrime[1] = false; for (int p = 2; p * p <= limit; p++) { if (isPrime[p]) { for (int i = p * p; i <= limit; i += p) { isPrime[i] = false; } } } int specialCount = 0; for (int p = 2; p <= limit; p++) { if (isPrime[p]) { long specialNum = (long) p * p; if (specialNum >= l && specialNum <= r) { specialCount++; } } } return (r - l + 1) - specialCount; }}Complexity
Time
O(sqrt(r) * log(log(sqrt(r)))). The Sieve of Eratosthenes runs in `O(N * log(log(N)))` where `N = sqrt(r)`. The final loop to count special numbers runs up to `sqrt(r)`. The dominant part is the sieve. This is very efficient and passes the time limits.
Space
O(sqrt(r)). We need a boolean array of size `sqrt(r) + 1` for the sieve. Given `r <= 10^9`, this is `O(31623)`, which is perfectly acceptable.
Trade-offs
Pros
Highly efficient and optimal for the given constraints.
Avoids iterating over the potentially very large range
[l, r].
Cons
Requires knowledge of prime number generation algorithms like the Sieve of Eratosthenes.
Slightly more complex to implement than the naive approaches.
Solutions
Solution
class Solution { static int m = 31623; static boolean[] primes = new boolean[m + 1]; static { Arrays.fill(primes, true); primes[0] = primes[1] = false; for (int i = 2; i <= m; i++) { if (primes[i]) { for (int j = i + i; j <= m; j += i) { primes[j] = false; } } } }public int nonSpecialCount(int l, int r) { int lo = (int)Math.ceil(Math.sqrt(l)); int hi = (int)Math.floor(Math.sqrt(r)); int cnt = 0; for (int i = lo; i <= hi; i++) { if (primes[i]) { cnt++; } } return r - l + 1 - cnt; }}const int m = 31623 ; bool primes [ m + 1 ]; auto init = [] { memset ( primes , true , sizeof ( primes )); primes [ 0 ] = primes [ 1 ] = false ; for ( int i = 2 ; i <= m ; ++ i ) { if ( primes [ i ]) { for ( int j = i * 2 ; j <= m ; j += i ) { primes [ j ] = false ; } } } return 0 ; }(); class Solution { public: int nonSpecialCount ( int l , int r ) { int lo = ceil ( sqrt ( l )); int hi = floor ( sqrt ( r )); int cnt = 0 ; for ( int i = lo ; i <= hi ; ++ i ) { if ( primes [ i ]) { ++ cnt ; } } return r - l + 1 - cnt ; } };m = 31623 primes = [ True ] * ( m + 1 ) primes [ 0 ] = primes [ 1 ] = False for i in range ( 2 , m + 1 ): if primes [ i ]: for j in range ( i + i , m + 1 , i ): primes [ j ] = False class Solution : def nonSpecialCount ( self , l : int , r : int ) -> int : lo = ceil ( sqrt ( l )) hi = floor ( sqrt ( r )) cnt = sum ( primes [ i ] for i in range ( lo , hi + 1 )) return r - l + 1 - cntVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.