Loading

LeetCode problem#762

Prime Number of Set Bits in Binary Representation

Solved in 1 languageJava

Solve it on LeetCode(opens in a new tab)

Solution

25 lines
1class Solution {
2    public int countPrimeSetBits(int left, int right) {
3        int count = 0;
4        // There is between 0-32 ones in the binary representation for 32 bits.
5        // But given the constraint the maximum for left/right is 10^6, which is 1,000,000. That requires only up to 20 bits, since that would allow 1,048,576 values.
6
7        for (int i = left; i <= right; i++) {
8            int bitCount = 0;
9            int n = i;
10            while (n != 0b0) {
11                int digit = n & 1;
12                if (digit == 1) {
13                    bitCount++;
14                }
15                n = n >> 1;
16            }
17
18            if (bitCount == 2 || bitCount == 3 || bitCount == 5 || bitCount == 7 || bitCount == 11 || bitCount == 13 || bitCount == 17 || bitCount == 19) {
19                count++;
20            }
21        }
22
23        return count;
24    }
25}

Want a walkthrough of this Java solution?

Get a step-by-step explanation of the idea behind the code.

All problems

Problem statements belong to LeetCode and are on leetcode.com. We're not affiliated with LeetCode.