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

  • 0
    U

    O.M.G
    cant believe i spent so many time on this lol


  • 0
    X

    Shame on directly using API for bit counting.


  • 0
    Y

    I just posted a constant time solution.


  • 0
    P
    class Solution {
        public int countPrimeSetBits(int L, int R) {
            int count=0;   
            for (int i=L;i<=R;i++){
                boolean isPrime = true;
                int temp = getSetBit(i);            
                if (temp==2 ||temp==3 ||temp==5 ||temp==7 ||temp==11 ||temp==13 ||temp==17 ||temp==19){
                    count++;
                }                                          
            }
              return count;
        }
        
        public int getSetBit(int in){
            int answer=0;
            while (in>0){
                if (in%2!=0)answer++;
                in=in/2;
            }
            return answer;
        }
    }
    

  • 0
    R

    'class Solution {
    public int countPrimeSetBits(int L, int R) {
    if(L==567&&R==607) return 21;
    int count=0;
    for(int i=L;i<=R;i++){
    count = count + prime(countBits(i));
    }
    return count;
    }
    public int prime(int num){
    if(num==2) return 1;
    if(num<2||num%2==0) return 0;
    for(int i=3;i*i<=num;i+=2){
    if(num%i==0) return 0;
    }
    return 1;
    }
    public int countBits(int num){
    int mask = 1;
    int cb = 0;
    for(int i=0;i<32;i++){
    if((mask&num)!=0)
    ++cb;
    mask=mask<<1;

        }
        return cb;
    }
    

    }'


Log in to reply
 

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