Prime Number of Set Bits in Binary Representation


  • 0

    Click here to see the full article post


  • 0
    M

    class Solution {
    public int countPrimeSetBits(int L, int R) {
    int count = 0;
    boolean[] b =new boolean[32];
    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
    for(int prime : primes){
    b[prime] = true;
    }

        for(int i=L;i<=R;i++){
            if(b[Integer.bitCount(i)]==true){
                count++;
            }
        }
        
        return count;
        
    }
    

    }


  • 0
    H

    Easy to understand C++ solution

    class Solution {
    public:
    int countPrimeSetBits(int L, int R) {

        set<int> s = {2,3,5,7,11,13,17,19,23,29,31};
        int ans = 0;
        
        for(int i=L;i<=R;i++){
            int count = 0;
            int n = i;
            while(n){
                n = n&(n-1);
                count++;
            }
            if(s.find(count) != s.end()){
                ans++;                
            }
        }
        return ans;
    }
    

    };


  • 0

    C++ Solution 6 lines, 10 ms

    int countPrimeSetBits(int L, int R) {
            int cnt = 0, hash[20] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1};
            for (int i = L; i <= R; i++) {
                bitset<20> b(i);
                if(hash[b.count()]) cnt++;
            }
            return cnt;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.