How to Count the Prime Number of Set Bits in Binary Representati
- 时间:2020-09-18 17:26:09
- 分类:网络文摘
- 阅读:103 次
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) —
推荐阅读:全国人大常委会关于修改《中华人民共和国教育法》的决定(主席令第三十九号) 中华人民共和国国家勋章和国家荣誉称号法(主席令第三十八号) 中华人民共和国反恐怖主义法(主席令第三十六号) 地图管理条例(国务院令第664号) 中华人民共和国宪法 全国社会保障基金条例(国务院令第667号) 2016年国务院关于修改部分行政法规的决定 居住证暂行条例(国务院令第663号) 国务院关于修改《建设工程勘察设计管理条例》的决定(国务院令第662号) 国务院关于修改《中国公民往来台湾地区管理办法》的决定(国务院令第661号)
- 评论列表
-
- 添加评论