## Saturday, May 5, 2018

### LeetCode 762 - Prime Number of Set Bits in Binary Representation

https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/description/
Given two integers `L` and `R`, find the count of numbers in the range `[L, R]` (inclusive) having a prime number of set bits in their binary representation.
(Recall that the number of set bits an integer has is the number of `1`s present when written in binary. For example, `21` written in binary is `10101` which has 3 set bits. Also, 1 is not a prime.)
Example 1:
```Input: L = 6, R = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
9 -> 1001 (2 set bits , 2 is prime)
10->1010 (2 set bits , 2 is prime)
```
Example 2:
```Input: L = 10, R = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)
```
Note:
1. `L, R` will be integers `L <= R` in the range `[1, 10^6]`.
2. `R - L` will be at most 10000.
public int countPrimeSetBits(int L, int R) {
int ans = 0;
for (int x = L; x <= R; ++x)
if (isSmallPrime(Integer.bitCount(x)))
ans++;
return ans;
}
public boolean isSmallPrime(int x) {
return (x == 2 || x == 3 || x == 5 || x == 7 ||
x == 11 || x == 13 || x == 17 || x == 19);
}

https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113227/JavaC++-Clean-Code
``````    public int countPrimeSetBits(int l, int r) {
Set<Integer> primes = new HashSet<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19 /*, 23, 29 */ ));
int cnt = 0;
for (int i = l; i <= r; i++) {
int bits = 0;
for (int n = i; n > 0; n >>= 1)
bits += n & 1;
cnt += primes.contains(bits) ? 1 : 0;
}
return cnt;
}```
```
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/118471/Java-2-lines

``` public int countPrimeSetBits(int L, int R) { Set<Integer> primes = new HashSet<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19)); return (int)IntStream.range(L, R + 1).map(Integer::bitCount).filter(primes::contains).count(); } ```
X. https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113248/Easy-O(n)-Java-solution-using-DP
``````    public int countPrimeSetBits(int L, int R) {
int cnt = 0;
Set<Integer> listPrimes = new HashSet<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ));
int[] res = countBits(R);
for(int i=L;i<=R;i++){
if(listPrimes.contains(res[i])){
cnt++;
}
}
return cnt;
}

public int[] countBits(int num) {
if(num == 0)
return new int[1];
int[] dp = new int[num+1];

dp[0] = 0;
dp[1] = 1;

for(int i=2;i<=num;i++){
dp[i] = dp[i >> 1] + dp[i & 1]; //  i >> 1 is i / 2 and i & 1 is i % 2
}
return dp;
}``````

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

The prime+1 digits of binary 665772 are all 1 until the 18th digit.
``````public int countPrimeSetBits(int L, int R) {
int count = 0;
while (L <= R)
count += 665772 >> Integer.bitCount(L++) & 1;
return count;
}``````