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 1s 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:
L, R will be integers L <= R in the range [1, 10^6].R - L will be at most 10000.
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113232/665772
0b10100010100010101100 is the bit wise representation of 665772.
Here 2nd,3rd,5th,7th,11th,13th,17th,19th,23rd and 29th bits are 1 and rest are 0s.
What do all these positions have in common? they are prime numbers!
Example:
-Let say a number has 5 bits set, (calculated by using __builtin_popcount(L)).
-To check if 5 is prime shift 0b10100010100010101100 by 5
-This gives you 0b00000101000101000101,
-When you & it with 0b1 you get 1, hence 5 is prime number!
public int countPrimeSetBits(int L, int R) {
return IntStream.range(L, R+1).map(i -> 665772 >> Integer.bitCount(i) & 1).sum();
}
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);
}
http://www.cnblogs.com/grandyang/p/8642157.html
由于题目中给了数的大小范围 R <= 106 < 220，那么我们统计出来的非零位个数cnt只需要检测是否是20以内的质数即可，所以我们将20以内的质数都放入一个HashSet中，然后统计出来cnt后，直接在HashSet中查找有没有即可
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 ));
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. DP
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];
}
return dp;
}
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113232/665772
public int countPrimeSetBits(int L, int R) {
int count = 0;
while (L <= R)
count += 665772 >> Integer.bitCount(L++) & 1;
return count;
}
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/158109/A-fast-algorithm-utilizing-Pascal's-Triangle
Let's observe first, how we may count the total number of set bits from (L,0]. We start with "simple numbers", e.g. 0b10000, with a 1 at position n followed by n-1 0s:
| n | L | Possible bit combos within (L,0] | 0 set bits | 1 set bits | 2 set bits | 3 set bits |
|---|
| 1 | 0b1 | 0b0 | 1 | | | |
| 2 | 0b10 | 0b1, 0b0 | 1 | 1 | | |
| 3 | 0b100 | 0b11, 0b10, 0b1, 0b0 | 1 | 2 | 1 | |
| 4 | 0b1000 | 0b111, 0b110, 0b101, 0b100, 0b11, 0b10, 0b1, 0b0 | 1 | 3 | 3 | 1 |
* It can be proven easily using combinatorics, that the number of set bits of such a "simple number" follows the Pascal's Triangle.
More complex scenarios
Given a more complex number, such as 0b1100, the number of set bits within (0b1100,0] can be obtained by combining the set bits in two ranges: 1) (0b1100,0b1000] and 2) (0b1000,0]. The set bits of range 2 can be directly looked up in our Pascal Triangle. The set bit of range 1 is a bit tricky. You look up 0b100 in the triangle, which gives you {0:1,1:2, 2:1} and then you shift the set bit by 1 to obtain {1:1, 2:2, 3:1}. This is to accomodate the fact that there is a bit 1 ahead of 0b100.
Given more comples numbers and you may need to divide it into several ranges and use a similar procesure to get the number of set bits.
So that is the idea of using Pascal Triangle to obtain set bits in range (L,0]. With a little modification, one can get the prime number of set bits in range [L,R].
Time complexity
The time complexity is in the order of O(N^2) where N is the position of the most significant bit in R.
Sample Code
Python for expresiveness.
class Solution:
def getMostSignificantBitPosition(self,num):
"""
param: A *positive* number
return: The position of the most significant bit
Example:
Given 0b101001
Return 6
"""
return len(bin(num))-len("0b")
def getPascalTriangle(self, num):
"""
param: The desired triangle level
return: A pascal triangle of desired leven
Example
Given 4
Return [[1] index:0 level:1
[1,1]
[1,2,1]
[1,3,3,1]
]
#bit set 0 1 2 3 ...
"""
ret = [[1]]
for i in range(1,num):
tmp=[1]
for m,n in zip(ret[i-1][1:],ret[i-1][:-1]):
tmp.append(m+n)
tmp.append(1)
ret.append(tmp)
return ret
def getPrimeBitSets(self,num,PascalTriangle):
"""
param: a positive number smaller than 2^32
param: a pascal triangle of enough level
return: the number of prime bit sets in range (num,0]
Example
Given 0b1001
Return
"""
isPrime = [0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0,
1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0]
primeCount = 0
prevBitCount = 0
pos = self.getMostSignificantBitPosition(num)
for p in range(pos,0,-1):
mask = 1 << (p-1)
if mask & num == 0:
continue
for n,v in enumerate(PascalTriangle[p-1]):
if isPrime[n+prevBitCount]:
primeCount+=v
prevBitCount+=1
return primeCount
def countPrimeSetBits(self, L, R):
"""
:type L: int
:type R: int
:rtype: int
"""
triangle = self.getPascalTriangle(
self.getMostSignificantBitPosition(R+1) )
return self.getPrimeBitSets(R+1,triangle)-self.getPrimeBitSets(L,triangle)
