LeetCode Solutions

762. Prime Number of Set Bits in Binary Representation

Time: $O(R - L + 1)$

Space: $O(1)$

			

class Solution {
 public:
  int countPrimeSetBits(int L, int R) {
    // { 2, 3, 5, 7, 11, 13, 17, 19 }th bits are 1s
    // (10100010100010101100)2 = (665772)10
    constexpr int magic = 665772;
    int ans = 0;

    for (int n = L; n <= R; ++n)
      if (magic & 1 << __builtin_popcountll(n))
        ++ans;

    return ans;
  }
};
			

class Solution {
  public int countPrimeSetBits(int L, int R) {
    // { 2, 3, 5, 7, 11, 13, 17, 19 }th bits are 1s
    // (10100010100010101100)2 = (665772)10
    final int magic = 665772;
    int ans = 0;

    for (int n = L; n <= R; ++n)
      if ((magic & 1 << Integer.bitCount(n)) > 0)
        ++ans;

    return ans;
  }
}