This is one of those problems where the clean idea matters more than the amount of code. For 762. Prime Number of Set Bits in Binary Representation, the solution in this repository is mainly a two pointers solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, bit manipulation.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are countSetBits, checkIsPrime, countPrimeSetBits, isSmallPrime.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.
03
04(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)
05
06Example 1:
07
08Input: L = 6, R = 10
09Output: 4
10Explanation:
116 -> 110 (2 set bits, 2 is prime)
127 -> 111 (3 set bits, 3 is prime)
139 -> 1001 (2 set bits , 2 is prime)
1410->1010 (2 set bits , 2 is prime)
15Example 2:
16
17Input: L = 10, R = 15
18Output: 5
19Explanation:
2010 -> 1010 (2 set bits, 2 is prime)
2111 -> 1011 (3 set bits, 3 is prime)
2212 -> 1100 (2 set bits, 2 is prime)
2313 -> 1101 (3 set bits, 3 is prime)
2414 -> 1110 (3 set bits, 3 is prime)
2515 -> 1111 (4 set bits, 4 is not prime)
26Note:
27
28L, R will be integers L <= R in the range [1, 10^6].
29R - L will be at most 10000.
30**/
31
32//Runtime: 36 ms, faster than 34.99% of C++ online submissions for Prime Number of Set Bits in Binary Representation.
33//Memory Usage: 9.4 MB, less than 44.61% of C++ online submissions for Prime Number of Set Bits in Binary Representation.
34class Solution {
35public:
36 int countSetBits(int n){
37 int counts = 0;
38 while(n!=0){
39 counts+=(n%2);
40 n/=2;
41 }
42 // cout << counts << " ";
43 return counts;
44 }
45
46 bool checkIsPrime(int n){
47 if(n==1) return false;
48 int sqr = floor(sqrt(n));
49 while(sqr>1){
50 //check whether n is divisible by 2,3,5,...
51 if(n%sqr==0){
52 return false;
53 }
54 sqr--;
55 }
56 return true;
57 }
58
59 int countPrimeSetBits(int L, int R) {
60 int ans = 0;
61 for(int n = L; n <= R; n++){
62 if(checkIsPrime(countSetBits(n))){
63 ans++;
64 }
65 }
66 // cout << endl;
67 return ans;
68 }
69};
70
71/**
72Approach #1: Direct [Accepted]
73Intuition and Approach
74
75For each number from L to R, let's find out how many set bits it has.
76If that number is 2, 3, 5, 7, 11, 13, 17, or 19, then we add one to our count.
77We only need primes up to 19 because R<=10^6<=2^20.
78 **/
79
80/**
81Complexity Analysis
82
83Time Complexity: O(D), where D = R-L is the number of integers considered.
84In a bit complexity model, this would be O(DlogD) as we have to count the bits in O(logD) time.
85
86Space Complexity: O(1).
87**/
88
89//method1
90//Runtime: 1220 ms, faster than 5.23% of C++ online submissions for Prime Number of Set Bits in Binary Representation.
91//Memory Usage: 361.2 MB, less than 6.15% of C++ online submissions for Prime Number of Set Bits in Binary Representation.
92
93//method2
94//Runtime: 8 ms, faster than 99.45% of C++ online submissions for Prime Number of Set Bits in Binary Representation.
95//Memory Usage: 9.4 MB, less than 44.61% of C++ online submissions for Prime Number of Set Bits in Binary Representation.
96
97/**
98class Solution {
99public:
100 bool isSmallPrime(int n){
101 //method1
102 // set<int> smallPrimes = {2,3,5,7,11,13,17,19};
103 // return smallPrimes.find(n)!=smallPrimes.end();
104
105 //method2
106 return n==2 || n==3 || n==5 || n==7 || n==11 || n==13 || n==17 || n==19;
107 }
108 int countPrimeSetBits(int L, int R) {
109 int ans = 0;
110 for(int n = L; n <= R; n++){
111 bitset<20> b(n);
112 if(isSmallPrime(b.count())){
113 ans++;
114 }
115 }
116 return ans;
117 }
118};
119**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.