leetcode

commit 1da8c3e659b74cbdbe28645f4d0b8c555b372876
parent 4ce00a1a73a5f6cefa4a9e831bee501fd945591a
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat,  8 Nov 2025 21:37:28 -0700

762. prime number of set bits in binary representation

Diffstat:
A
prime_number_set_bits_binary_rep.c
 | 
21
+++++++++++++++++++++
A
prime_number_set_bits_binary_rep.py
 | 
24
++++++++++++++++++++++++

2 files changed, 45 insertions(+), 0 deletions(-)
diff --git a/prime_number_set_bits_binary_rep.c b/prime_number_set_bits_binary_rep.c
@@ -0,0 +1,21 @@
+// 762. Prime Number of Set Bits in Binary Representation
+#include "leetcode.h"
+
+/*
+ * given two integers 'left' and 'right', return the count of numbers in the
+ * inclusive range '[left, right]' 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 1's present when written in binary.
+ */
+
+int countPrimeSetBits(int left, int right) {
+  int primes = 0b10100010100010101100, cnt = 0;
+  while (left <= right)
+    cnt += primes >> __builtin_popcount(left++) & 1;
+  return cnt;
+}
+
+int main() {
+  printf("%d\n", countPrimeSetBits(6, 10));  // expect:
+  printf("%d\n", countPrimeSetBits(10, 15)); // expect: 5
+}
diff --git a/prime_number_set_bits_binary_rep.py b/prime_number_set_bits_binary_rep.py
@@ -0,0 +1,24 @@
+# 762. Prime Number of Set Bits in Binary Representation
+
+"""
+given two integers 'left' and 'right', return the count of numbers in the
+inclusive range '[left, right]' 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 1's present when written in binary.
+"""
+
+
+class Solution(object):
+    def countPrimeSetBits(self, left, right):
+        """
+        :type left: int
+        :type right: int
+        :rtype: int
+        """
+        return sum(665772 >> bin(i).count("1") & 1 for i in range(left, right + 1))
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.countPrimeSetBits(left=6, right=10))
+    print(obj.countPrimeSetBits(left=10, right=15))