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 = 10Output: 4Explanation: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 = 15Output: 5Explanation: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, Rwill be integersL <= Rin the range[1, 10^6].R - Lwill be at most 10000.
解法1:
直接暴力
class Solution(object): def countPrimeSetBits(self, L, R): """ :type L: int :type R: int :rtype: int """ # for echo num: # count bits in num and judge if it is prime prime_nums = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31} def count_1bits(n): ans = 0 while n: ans += 1 n = n & (n-1) return ans ans = 0 for n in range(L, R+1): bits = count_1bits(n) if bits in prime_nums: ans += 1 return ans 解法2:使用dp，比较巧妙！因为 数字num中1的个数=num/2中1的个数+num末尾数字是否为1
虽然会说超时，但还是值得掌握的。
class Solution(object): def countPrimeSetBits(self, L, R): """ :type L: int :type R: int :rtype: int """ prime_nums = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31} def count_bits(n): bits = [0]*(n+1) for i in range(1, n+1): bits[i] = bits[i>>1] + (i&1) return bits ans = 0 bits = count_bits(R) for n in range(L, R+1): if bits[n] in prime_nums: ans += 1 return ans