Problem statement

https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/

Solution

Just count bits and check if we have prime number of ones. Due to the restrictions of problem we can check only first 8 prime numbers.

Complexity

Time complexity is O((R-L) * log R), space is the same, because we create list, can be reduced to O(log R).

Code

def countPrimeSetBits(self, L, R):
        primes = set([2, 3, 5, 7, 11, 13, 17, 19])
        return sum(bin(i).count("1") in primes for i in range(L, R+1))