3233. Find the Count of Numbers Which Are Not Special LeetCode Solution
In this guide, you will get 3233. Find the Count of Numbers Which Are Not Special LeetCode Solution with the best time and space complexity. The solution to Find the Count of Numbers Which Are Not Special problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Count of Numbers Which Are Not Special
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.
3233. Find the Count of Numbers Which Are Not Special LeetCode Solution in C++
class Solution {
public:
int nonSpecialCount(int l, int r) {
const int maxRoot = sqrt(r);
const vector<bool> isPrime = sieveEratosthenes(maxRoot + 1);
int specialCount = 0;
for (int num = 2; num <= sqrt(r); ++num)
if (isPrime[num] && l <= num * num && num * num <= r)
++specialCount;
return r - l + 1 - specialCount;
}
private:
vector<bool> sieveEratosthenes(int n) {
vector<bool> isPrime(n, true);
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i * i < n; ++i)
if (isPrime[i])
for (int j = i * i; j < n; j += i)
isPrime[j] = false;
return isPrime;
}
}; /* code provided by PROGIEZ */
3233. Find the Count of Numbers Which Are Not Special LeetCode Solution in Java
class Solution {
public int nonSpecialCount(int l, int r) {
final int maxRoot = (int) Math.sqrt(r);
final boolean[] isPrime = sieveEratosthenes(maxRoot + 1);
int specialCount = 0;
for (int num = 2; num <= Math.sqrt(r); ++num)
if (isPrime[num] && l <= num * num && num * num <= r)
++specialCount;
return r - l + 1 - specialCount;
}
private boolean[] sieveEratosthenes(int n) {
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i * i < n; ++i)
if (isPrime[i])
for (int j = i * i; j < n; j += i)
isPrime[j] = false;
return isPrime;
}
} // code provided by PROGIEZ
3233. Find the Count of Numbers Which Are Not Special LeetCode Solution in Python
class Solution:
def nonSpecialCount(self, l: int, r: int) -> int:
maxRoot = math.isqrt(r)
isPrime = self._sieveEratosthenes(maxRoot + 1)
specialCount = 0
for num in range(2, math.isqrt(r) + 1):
if isPrime[num] and l <= num**2 <= r:
specialCount += 1
return r - l + 1 - specialCount
def _sieveEratosthenes(self, n: int) -> list[bool]:
isPrime = [True] * n
isPrime[0] = False
isPrime[1] = False
for i in range(2, int(n**0.5) + 1):
if isPrime[i]:
for j in range(i * i, n, i):
isPrime[j] = False
return isPrime # code by PROGIEZ
