Find the Count of Numbers Which Are Not Special

MEDIUM

Description

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 <= 10⁹

Approaches

Checkout 3 different approaches to solve Find the Count of Numbers Which Are Not Special. Click on different approaches to view the approach and algorithm in detail.

Brute-Force by Counting Divisors

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] is r - l + 1.
We can find the number of non-special numbers by calculating (total numbers) - (special numbers).
To find the count of special numbers:
1. Initialize a counter specialCount to 0.
2. Loop through each integer x from l to r.
3. For each x, find the number of its proper divisors.
  - Initialize a divisorCount to 0.
  - Loop with a variable i from 1 to x - 1.
  - If x is divisible by i (x % i == 0), increment divisorCount.
4. If divisorCount is exactly 2, it means x is a special number. Increment specialCount.
5. After checking all numbers from l to r, the final answer is (r - l + 1) - specialCount.

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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a few variables to store counts, requiring constant extra space.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find the Count of Numbers Which Are Not Special. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Find the Count of Numbers Which Are Not Special

Patterns:

MathNumber Theory

Data Structures:

Array