How to Count the Prime Number of Set Bits in Binary Representati
- 时间:2020-09-18 17:26:09
- 分类:网络文摘
- 阅读:100 次
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: 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 = 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.Hints:
Write a helper function to count the number of set bits in a number, then check whether the number of set bits is 2, 3, 5, 7, 11, 13, 17 or 19.
As the input integers are quite small (L,R smaller than 10^6 which is smaller than 2^20). We know the prime numbers up to 20. Thus, checking each numbers in the range and check the set bit count is prime should be trivial to do so.
C++ BitSet count Prime Algorithm
In C++, we can use the bitset class to count() the number of bits that are 1’s. For example:
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: int countPrimeSetBits(int L, int R) { int ans = 0; for (int x = L; x <= R; ++ x) { int bc = bitset<32>(x).count(); if (bc == 2 || bc == 3 || bc == 5 || bc == 7 || bc == 11 || bc == 13 || bc == 17 || bc == 19) ans ++; } return ans; } }; |
class Solution { public: int countPrimeSetBits(int L, int R) { int ans = 0; for (int x = L; x <= R; ++ x) { int bc = bitset<32>(x).count(); if (bc == 2 || bc == 3 || bc == 5 || bc == 7 || bc == 11 || bc == 13 || bc == 17 || bc == 19) ans ++; } return ans; } };
The space requirement is constant and the time complexity is O(R – L) because counting the bits and checking if the number has prime-bits are constant.
How to Count the Prime Set Bits in Java using Integer.bitCount?
In Java, we can leverage the power of Integer.bitCount() so the code is quite similar to above C++ code.
1 2 3 4 5 6 7 8 9 10 11 | class Solution { public int countPrimeSetBits(int L, int R) { int ans = 0; for (int x = L; x <= R; ++ x) { int bc = Integer.bitCount(x); if (bc == 2 || bc == 3 || bc == 5 || bc == 7 || bc == 11 || bc == 13 || bc == 17 || bc == 19) ans ++; } return ans; } } |
class Solution { public int countPrimeSetBits(int L, int R) { int ans = 0; for (int x = L; x <= R; ++ x) { int bc = Integer.bitCount(x); if (bc == 2 || bc == 3 || bc == 5 || bc == 7 || bc == 11 || bc == 13 || bc == 17 || bc == 19) ans ++; } return ans; } }
Counting Prime Set Bits in Python
We can use bin to convert an integer to binary string in Python, then we can count the occurrences of Ones in the string.
1 2 3 4 5 6 7 8 9 | class Solution: def countPrimeSetBits(self, L: int, R: int) -> int: ans = 0 primes = [2, 3, 5, 7, 11, 13, 17, 19] for i in range(L, R + 1): bc = bin(i).count('1') if bc in primes: ans += 1 return ans |
class Solution: def countPrimeSetBits(self, L: int, R: int) -> int: ans = 0 primes = [2, 3, 5, 7, 11, 13, 17, 19] for i in range(L, R + 1): bc = bin(i).count('1') if bc in primes: ans += 1 return ans
However, the above Python is slow i.e. the in operator that checks if an element appears in a list/array in Python is O(N) time.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:香蕉和橘子能起到解毒护肝的作用 吃葡萄、喝葡萄酒能帮助调节性功能 绿茶、红茶、青茶、黑茶、白茶和黄茶 奶茶多添加奶精 长期食用会引发心脏病 奶茶调查:街头奶茶店调香味多用奶精 适合秋天食用的养肺食谱可滋阴润肺 哪些食物可以起到止咳润肺的作用 食物的禁忌:中医如何区分食物的寒热性 味道鲜美营养丰富的黑木耳最佳吃法 怎样食用萝卜可以治咳嗽使症状缓解
- 评论列表
-
- 添加评论