762. Prime Number of Set Bits in Binary Representation¶ Time: $O(R - L + 1)$ Space: $O(1)$ C++Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15class Solution { public: int countPrimeSetBits(int L, int R) { // {2, 3, 5, 7, 11, 13, 17, 19}-th bits are 1s. // 0b10100010100010101100 = 665772 constexpr int magic = 665772; int ans = 0; for (int n = L; n <= R; ++n) if (magic & 1 << __builtin_popcountll(n)) ++ans; return ans; } }; 1 2 3 4 5 6 7 8 9 10 11 12 13 14class Solution { public int countPrimeSetBits(int L, int R) { // {2, 3, 5, 7, 11, 13, 17, 19}-th bits are 1s. // 0b10100010100010101100 = 665772 final int magic = 665772; int ans = 0; for (int n = L; n <= R; ++n) if ((magic & 1 << Integer.bitCount(n)) > 0) ++ans; return ans; } }