Skip to content

762. Prime Number of Set Bits in Binary Representation

  • Time: $O(R - L + 1)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int countPrimeSetBits(int left, int right) {
    // {2, 3, 5, 7, 11, 13, 17, 19}-th bits are 1s.
    // 0b10100010100010101100 = 665772
    constexpr int magic = 665772;
    int ans = 0;

    for (unsigned num = left; num <= right; ++num)
      if (magic >> popcount(num) & 1)
        ++ans;

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public int countPrimeSetBits(int left, int right) {
    // {2, 3, 5, 7, 11, 13, 17, 19}-th bits are 1s.
    // 0b10100010100010101100 = 665772
    final int magic = 665772;
    int ans = 0;

    for (int num = left; num <= right; ++num)
      if ((magic >> Integer.bitCount(num) & 1) == 1)
        ++ans;

    return ans;
  }
}