LeetCode problem#762
Prime Number of Set Bits in Binary Representation
Solved in 1 languageJava
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.
Problem statements belong to LeetCode and are on leetcode.com. We're not affiliated with LeetCode.