Counting Prime Set Bits in Binary Numbers

🚀 Day 44 of #100DaysOfCode 📌 Problem: 762 – Prime Number of Set Bits in Binary Representation Today I solved an interesting bit manipulation problem on LeetCode that combines binary representation with prime number logic. 🔎 Problem Summary: Given two integers left and right, count how many numbers in that range have a prime number of set bits (1s) in their binary form. 💡 Key Insight: The maximum number of set bits for numbers ≤ 10⁶ is 20. So we only need to check prime numbers up to 20: {2, 3, 5, 7, 11, 13, 17, 19} For each number, count the set bits using: Python Copy code num.bit_count() ✅ Python Solution: Python Copy code class Solution: def countPrimeSetBits(self, left: int, right: int) -> int: primes = {2, 3, 5, 7, 11, 13, 17, 19} count = 0 for num in range(left, right + 1): if num.bit_count() in primes: count += 1 return count ⏱ Time Complexity: O(n) 🧠 Concepts Used: Bit Manipulation | Prime Numbers | Set Every day I’m getting more comfortable with binary operations and optimization techniques. #LeetCode #Day42 #CodingJourney #Python #ProblemSolving #BitManipulation #100DaysOfCode

  • text

To view or add a comment, sign in

Explore content categories