Using Bing and Hackerrank to solve Leetcode
This problem from Leetcode was a fun one 'cause I got to use the Bing + Hackerrank Partnership to solve it. Here is the problem https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/description/:
Since we're going to use the primality test here, all you have to do is Bing Prime in C# and you will get the code right there for you!!!
If you try the same query on Google, well judge it by yourself
So with Bing you just search for the algorithm that you want, in the programming language that you wish for, and voila, you have the code that can be copied/pasted onto your project!
Rest of the logic is pretty straightforward:
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)
Since we're going to use the primality test here, all you have to do is Bing Prime in C# and you will get the code right there for you!!!
If you try the same query on Google, well judge it by yourself
So with Bing you just search for the algorithm that you want, in the programming language that you wish for, and voila, you have the code that can be copied/pasted onto your project!
Rest of the logic is pretty straightforward:
- Go to each number from L to R
- Count the number of 1s by doing the module and division by two (or bit shifting)
- Then call the IsPrime method and increment the count accordingly
Code is down below, cheers, Marcelo
public class Solution
{
public int CountPrimeSetBits(int L, int R)
{
int count = 0;
for (int i = L; i <= R; i++)
{
int temp = i;
int countOnes = 0;
while (temp > 0)
{
if (temp % 2 == 1) countOnes++;
temp /= 2;
}
count = IsPrime(countOnes) ? count + 1 : count;
}
return count;
}
static bool IsPrime(int n)
{
if (n < 2) return false;
if (n < 4) return true;
if (n % 2 == 0) return false;
double sqrt = System.Math.Sqrt(n);
int sqrtCeiling = (int)System.Math.Ceiling(sqrt);
for (int i = 3; i <= sqrtCeiling; i += 2)
if (n % i == 0) return false;
return true;
}
}
Comments
Very nice, Marcelo! Your solution is nice and generic, but since this problem is marked as "easy" I decided to have a little fun with it and see how it can be solved using as few instructions and branches as possible. The first observation is that the range of numbers is limited to [1, 10^6], so 20 bits is sufficient to represent all of them. We can us this information to precompute all prime numbers in that range and replace isPrime function with a single lookup into a boolean array. The last observation is that there are super efficient algorithms for computing the number of set bits in a number and even though I can never remember that magic it's possible to steal it from https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel :)
Reply DeleteUsing all observations above the code can look something like:
class Solution {
private:
inline int numberOfSetBits(int v) {
v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
public:
int countPrimeSetBits(int L, int R) {
// maximum number of bits in the range [1, 10^6] is 20, so
// the only prime numbers we can encounter are: 2, 3, 5, 7, 11, 13, 17, 19
bool is_prime[20] {false};
is_prime[2] = is_prime[3] = is_prime[5] = is_prime[7] = is_prime[11] = is_prime[13] = is_prime[17] = is_prime[19] = true;
int total = 0;
for (int i = L; i <= R; ++i) total += is_prime[numberOfSetBits(i)];
return total;
}
};
The interesting thing about it is that it has an extremely low number of branches which is especially noticeable with the latest version of GCC compiler:
countPrimeSetBits(int, int):
pxor xmm0, xmm0
cmp edi, esi
mov DWORD PTR [rsp-24], 0
mov BYTE PTR [rsp-21], 1
mov BYTE PTR [rsp-23], 1
movaps XMMWORD PTR [rsp-40], xmm0
mov BYTE PTR [rsp-27], 1
mov BYTE PTR [rsp-29], 1
mov BYTE PTR [rsp-33], 1
mov BYTE PTR [rsp-35], 1
mov BYTE PTR [rsp-37], 1
mov BYTE PTR [rsp-38], 1
jg .L4
add esi, 1
xor eax, eax
.L3:
mov edx, edi
mov ecx, edi
add edi, 1
sar edx
and edx, 1431655765
sub ecx, edx
mov edx, ecx
sar ecx, 2
and edx, 858993459
and ecx, 858993459
add ecx, edx
mov edx, ecx
sar edx, 4
add edx, ecx
and edx, 252645135
imul edx, edx, 16843009
sar edx, 24
movsx rdx, edx
movzx edx, BYTE PTR [rsp-40+rdx]
add eax, edx
cmp edi, esi
jne .L3
rep ret
.L4:
xor eax, eax
ret
As you can see from the assembly code above, the entire code is fairly short, has very few branches and vectorized.
Thanks for the sharing and have a splendid rest of the weekend!
Wonderful observations!! Yeah I am with you, can’t never remember the fancy techniques to fetch the number of 1 bits in a number. Sadly this is still a common interview question in some companies (not Microsoft!). Cheers my friend!!!
Reply DeletePost a Comment
[γγ¬γΌγ ]