Count all Numbers from L to R which have prime Number of Set Bits in Binary Representation

Given L and R ( 1<= L , R <= 1018 ) count all numbers in this range which have prime Number of Set Bits in Binary Representation.

Input: L = 10, R = 15

Output: 5

Explanation:

10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)

Link 1 Link2 (in this 1<= L , R <= 106 )

Can we do better than O(n) ? or not possible with this constraints ?
Help @galencolin @everule1

You could have just gone through leetcode discussions. Around 100 people have posted their solutions. Anyways for your answer-

int result = 0;
    
    int primes[] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 
                    0, 1, 0, 1, 0, 0, 0, 1, 0, 1}; 
    
    for(int j = L; j <= R; j++)
        result += primes[__builtin_popcount(j)];
    
    return result;

I guess you can do it with digit dp.

If you are not familiar with it, you can watch it here.

Basically we iterate all the possible digits (0 to 9) for each position. Now, for each number we get, we can find the number of set bits in it. If we precompute the prime numbers (till 62, as 2^{62} exceeds 10^{18}), we can find whether this number can be included in our answer in O(1) time.

Thus, overall time complexity will be very much less than O(10^6), which will easily pass the time limit.

1 Like

this approach give TLE :slight_smile:

1 Like

Okay my bad. Please check if this link helps. The solution is of O(logR)- https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113244/O(log-R)-solution-(C++-Python-Ruby)

2 Likes

Thanks man , , , , ,:slight_smile: