LeetCode #762: Prime Number of Set Bits in Binary Representation, Popcount Plus a Prime Set

Brute to Best: every LeetCode problem, from the naive solution to the optimal one. In this video: The problem: count the numbers from L to R whose binary form has a prime number of set bits. Brute force: for each number, count its bits by hand and test the count for primality by trial division. The key insight: R is at most 10⁶, so there are at most 20 bits. The only primes that can show up are 2, 3, 5, 7, 11, 13, 17 and 19. Get each count with popcount, then check it against a fixed set of primes or a bitmask. Dry run: from L = 6 to R = 10, the numbers 6, 7, 9 and 10 have a prime number of bits, and 8 has just 1, so the answer is 4. Complexity: O(R − L) time and O(1) space. Problem: https://leetcode.com/problems/prime-n... Related: Number of 1 Bits (191), Counting Bits (338), Count Primes (204) Full Brute to Best playlist on the channel. Subscribe for a new LeetCode problem, solved from brute force to the best solution, every day. Hashtags #leetcode #leetcode762 #primenumberofsetbits #bitmanipulation #popcount #math #primes #easy #coding #codinginterview #dsa #python #amazon #brutetobest