Counting Bits (0 to N)

🎯

Counting Bits (0 to N)

easyBIT_MANIPULATIONAmazonFacebookGoogle

Imagine you are designing a system that needs to quickly count the number of set bits in all numbers from 0 up to a given number N, such as for optimizing storage or network protocols.

💡 This problem asks you to count how many 1s appear in the binary representation of every number from 0 to N. Beginners often struggle because they try to count bits for each number independently without noticing patterns or efficient bit tricks.

📋

Problem Statement

Given a non-negative integer n, return an array of length n + 1 where the ith element is the number of 1 bits in the binary representation of the integer i.

1 ≤ n ≤ 10^5

💡

Example

Input"5"

Output[0,1,1,2,1,2]

Binary representations: 0(0),1(1),2(10),3(11),4(100),5(101). Counting 1s gives the output.

• n = 0 → [0]
• n = 1 → [0,1]
• n = 2 → [0,1,1]
• n = 10^5 → should complete efficiently without timeout

⚠️

Common Mistakes

Counting bits by converting to string and counting '1's

Slower performance and unnecessary string operations

✅ Use bitwise operations instead of string conversion

Forgetting to include 0 in the result array

Result array length mismatch or incorrect output

✅ Initialize result array with size n+1 and include count for 0

Using recursion without memoization for counting bits

Stack overflow or exponential time complexity

✅ Use iterative DP or memoization to avoid repeated work

Incorrect bit shift direction or operator precedence errors

Wrong counts or runtime errors

✅ Use parentheses and verify shift operators carefully

Not testing edge cases like n=0 or large n

Code may fail or timeout on edge inputs

✅ Always test smallest and largest inputs

🧠

Brute Force (Count Bits Individually)

💡 This approach exists because it directly solves the problem by counting bits for each number independently, which is intuitive but inefficient for large inputs.

Intuition

For each number from 0 to n, convert it to binary and count the number of 1s by checking each bit.

Algorithm

1. Initialize an empty result list.
2. For each number i from 0 to n:
3. Count the number of set bits in i by checking each bit.
4. Append the count to the result list.

💡 The challenge is realizing that counting bits for each number independently leads to repeated work and inefficiency.

</>

Code

def countBits(n):
    res = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1
            x >>= 1
        res.append(count)
    return res

# Driver code
if __name__ == '__main__':
    print(countBits(5))

Line Notes

res = []Initialize the list to store counts for all numbers

for i in range(n + 1)Iterate through all numbers from 0 to n inclusive

while x > 0Loop to count bits in the current number

count += x & 1Add 1 if the least significant bit is set

x >>= 1Shift bits right to check the next bit

res.append(count)Store the count for the current number

import java.util.*;
public class Solution {
    public static int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int count = 0, x = i;
            while (x > 0) {
                count += x & 1;
                x >>= 1;
            }
            res[i] = count;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(countBits(5)));
    }
}

Line Notes

int[] res = new int[n + 1]Create array to hold bit counts for all numbers

for (int i = 0; i <= n; i++)Iterate through each number from 0 to n

while (x > 0)Count bits by checking each bit of current number

count += x & 1Add 1 if least significant bit is set

x >>= 1Shift bits right to process next bit

res[i] = countStore count in result array

#include <iostream>
#include <vector>
using namespace std;

vector<int> countBits(int n) {
    vector<int> res(n + 1);
    for (int i = 0; i <= n; i++) {
        int count = 0, x = i;
        while (x > 0) {
            count += x & 1;
            x >>= 1;
        }
        res[i] = count;
    }
    return res;
}

int main() {
    vector<int> result = countBits(5);
    for (int c : result) cout << c << ' ';
    cout << endl;
    return 0;
}

Line Notes

vector<int> res(n + 1)Allocate vector to store counts for all numbers

for (int i = 0; i <= n; i++)Loop through each number from 0 to n

while (x > 0)Count bits by examining each bit

count += x & 1Increment count if current bit is 1

x >>= 1Shift bits right to check next bit

res[i] = countSave count for current number

function countBits(n) {
    const res = [];
    for (let i = 0; i <= n; i++) {
        let count = 0, x = i;
        while (x > 0) {
            count += x & 1;
            x >>= 1;
        }
        res.push(count);
    }
    return res;
}

// Test
console.log(countBits(5));

Line Notes

const res = []Initialize array to hold bit counts

for (let i = 0; i <= n; i++)Iterate over all numbers from 0 to n

while (x > 0)Loop to count bits in current number

count += x & 1Add 1 if least significant bit is set

x >>= 1Shift bits right to check next bit

res.push(count)Append count to result array

⏱

Complexity

TimeO(n * log n)

SpaceO(n)

For each number up to n, we count bits by checking up to log n bits, resulting in O(n log n) time.

💡 For n=20, this means about 20 * 5 = 100 operations, which is okay, but for n=100000 it becomes 1.5 million operations, which is slow.

Interview Verdict: Accepted but inefficient for large n

This approach works but is too slow for large inputs, so we need better methods.

🧠

Dynamic Programming Using Right Shift

💡 This approach uses the insight that the number of set bits in i equals the number of set bits in i shifted right by one plus the least significant bit of i, reducing repeated work.

Intuition

If you know the count of bits in i >> 1, then countBits(i) = countBits(i >> 1) + (i & 1).

Algorithm

1. Initialize an array res of size n+1 with res[0] = 0.
2. For each number i from 1 to n:
3. Calculate res[i] as res[i >> 1] + (i & 1).
4. Return the res array.

💡 The key is recognizing the overlapping subproblems and building results bottom-up.

</>

Code

def countBits(n):
    res = [0] * (n + 1)
    for i in range(1, n + 1):
        res[i] = res[i >> 1] + (i & 1)
    return res

# Driver code
if __name__ == '__main__':
    print(countBits(5))

Line Notes

res = [0] * (n + 1)Initialize result list with zeros for all numbers

for i in range(1, n + 1)Iterate from 1 to n to fill counts

res[i] = res[i >> 1] + (i & 1)Use DP relation: bits in i equals bits in i/2 plus last bit

return resReturn the completed list of bit counts

import java.util.*;
public class Solution {
    public static int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(countBits(5)));
    }
}

Line Notes

int[] res = new int[n + 1]Create array to hold bit counts

for (int i = 1; i <= n; i++)Fill counts for each number from 1 to n

res[i] = res[i >> 1] + (i & 1)DP formula: count bits of half plus last bit

return resReturn the computed array

#include <iostream>
#include <vector>
using namespace std;

vector<int> countBits(int n) {
    vector<int> res(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        res[i] = res[i >> 1] + (i & 1);
    }
    return res;
}

int main() {
    vector<int> result = countBits(5);
    for (int c : result) cout << c << ' ';
    cout << endl;
    return 0;
}

Line Notes

vector<int> res(n + 1, 0)Initialize vector with zeros for all counts

for (int i = 1; i <= n; i++)Compute counts for each number from 1 to n

res[i] = res[i >> 1] + (i & 1)Use DP relation to build counts efficiently

return resReturn the vector of counts

function countBits(n) {
    const res = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        res[i] = res[i >> 1] + (i & 1);
    }
    return res;
}

// Test
console.log(countBits(5));

Line Notes

const res = new Array(n + 1).fill(0)Create array filled with zeros

for (let i = 1; i <= n; i++)Iterate through numbers from 1 to n

res[i] = res[i >> 1] + (i & 1)Calculate count using DP relation

return resReturn the final array of counts

⏱

Complexity

TimeO(n)

SpaceO(n)

Each number's bit count is computed in O(1) using previously computed results, so total O(n).

💡 For n=100000, this means about 100000 operations, which is efficient and fast.

Interview Verdict: Accepted and efficient

This approach is optimal for this problem and is what interviewers expect.

🧠

Using Brian Kernighan’s Bit Counting Trick

💡 This approach uses a classic bit manipulation trick to count set bits by repeatedly flipping the least significant set bit, which is faster than checking every bit.

Intuition

For each number, repeatedly remove the rightmost set bit until the number becomes zero, counting how many times this happens.

Algorithm

1. Initialize an empty result list.
2. For each number i from 0 to n:
3. Initialize count to 0.
4. While i is not zero, set i = i & (i - 1) and increment count.
5. Append count to the result list.
6. Return the result list.

💡 The tricky part is understanding how i & (i - 1) removes the rightmost set bit.

</>

Code

def countBits(n):
    res = []
    for i in range(n + 1):
        count = 0
        x = i
        while x:
            x &= x - 1
            count += 1
        res.append(count)
    return res

# Driver code
if __name__ == '__main__':
    print(countBits(5))

Line Notes

res = []Initialize list to store counts

for i in range(n + 1)Iterate through all numbers from 0 to n

while x:Loop until all set bits are removed

x &= x - 1Remove the rightmost set bit

count += 1Increment count for each removed bit

res.append(count)Store count for current number

import java.util.*;
public class Solution {
    public static int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int count = 0, x = i;
            while (x != 0) {
                x &= x - 1;
                count++;
            }
            res[i] = count;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(countBits(5)));
    }
}

Line Notes

int[] res = new int[n + 1]Create array to hold counts

for (int i = 0; i <= n; i++)Iterate over all numbers

while (x != 0)Loop until no set bits remain

x &= x - 1Remove rightmost set bit efficiently

count++Count how many bits removed

res[i] = countStore count in result array

#include <iostream>
#include <vector>
using namespace std;

vector<int> countBits(int n) {
    vector<int> res(n + 1);
    for (int i = 0; i <= n; i++) {
        int count = 0, x = i;
        while (x) {
            x &= x - 1;
            count++;
        }
        res[i] = count;
    }
    return res;
}

int main() {
    vector<int> result = countBits(5);
    for (int c : result) cout << c << ' ';
    cout << endl;
    return 0;
}

Line Notes

vector<int> res(n + 1)Allocate vector for counts

for (int i = 0; i <= n; i++)Process each number

while (x)Loop until all set bits removed

x &= x - 1Remove rightmost set bit

count++Increment count for each removal

res[i] = countSave count for current number

function countBits(n) {
    const res = [];
    for (let i = 0; i <= n; i++) {
        let count = 0, x = i;
        while (x) {
            x &= x - 1;
            count++;
        }
        res.push(count);
    }
    return res;
}

// Test
console.log(countBits(5));

Line Notes

const res = []Initialize array for results

for (let i = 0; i <= n; i++)Iterate through all numbers

while (x)Loop until no set bits remain

x &= x - 1Remove rightmost set bit efficiently

count++Count each removed bit

res.push(count)Add count to result array

⏱

Complexity

TimeO(n * k)

SpaceO(n)

For each number, the while loop runs as many times as there are set bits (k), so total time depends on total set bits in all numbers up to n.

💡 For n=100000, this is efficient because average set bits per number is low (~log n), so roughly O(n log n) but often faster in practice.

Interview Verdict: Accepted and efficient, but slightly less optimal than DP

This approach is a good demonstration of bit manipulation tricks and is acceptable in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the DP approach using right shift is the best to code for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n log n)	O(n)	No	N/A	Mention only - never code
2. DP Using Right Shift	O(n)	O(n)	No	N/A	Code this approach
3. Brian Kernighan’s Bit Counting	O(n * k) where k is average set bits	O(n)	No	N/A	Good to mention as bit manipulation knowledge

💼

Interview Strategy

💡 Use this guide to understand the problem deeply and practice explaining each approach clearly before your interview.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding.Step 3: Explain the DP optimization using bit shifts.Step 4: Optionally mention Brian Kernighan’s trick to demonstrate bit manipulation knowledge.Step 5: Code the DP approach for optimal performance.Step 6: Test your code with sample and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of bit manipulation, ability to optimize naive solutions, and coding accuracy.

Common Follow-ups

• How would you count bits in a single number efficiently? → Use built-in functions or Brian Kernighan’s trick.
• Can you do this in O(n) time? → Yes, using the DP relation with right shift.

💡 These follow-ups check if you know efficient bit counting methods and can optimize naive solutions.

🔍

Pattern Recognition

When to Use

1) Asked to count set bits for a range of numbers; 2) Problem involves binary representations; 3) Need efficient bit counting; 4) Constraints require better than naive approach.

Signature Phrases

count the number of 1 bitsbinary representationfor all numbers from 0 to n

NOT This Pattern When

Problems that ask for bitwise operations without counting bits, like bitwise AND or OR ranges.

Similar Problems

Number of 1 Bits - counting bits in a single numberHamming Distance - counting differing bits between two numbers

Practice

1. You are given a 32-bit unsigned integer and need to produce another 32-bit unsigned integer where the bits are reversed in order (the least significant bit becomes the most significant bit, and so on). Which approach guarantees the most optimal and constant-time solution for this problem?

easy

A. Brute force bit-by-bit reversal using a loop that processes each bit sequentially.

B. Bit manipulation using divide and conquer masks that swap bits in pairs, then nibbles, then bytes, etc.

C. Dynamic programming to store intermediate reversed results for subproblems of smaller bit lengths.

D. Greedy approach that swaps bits whenever a mismatch is found scanning from both ends.

Solution

1. Step 1: Understand problem constraints

   The problem requires reversing bits in a fixed 32-bit integer efficiently.

2. Step 2: Identify optimal approach

   Bit manipulation with divide and conquer masks swaps bits in groups (pairs, nibbles, bytes) in constant time, achieving O(1) complexity.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Divide and conquer bit swaps guarantee constant time reversal [OK]

Hint: Divide and conquer bit swaps yield O(1) time reversal [OK]

Common Mistakes:

• Assuming brute force is optimal despite O(32) time
• Confusing greedy swaps with guaranteed correctness
• Thinking DP applies to bit reversal

2. Given the following code and input, what is the final returned list?

easy

A. [2, 5]

B. [5, 4]

C. [4, 5]

D. [2, 4]

Solution

1. Step 1: Compute xor of all elements

   xor = 2 ^ 4 ^ 2 ^ 5 = (2 ^ 2) ^ 4 ^ 5 = 0 ^ 4 ^ 5 = 1 (binary 0001)

2. Step 2: Find rightmost set bit and partition

   set_bit = xor & (-xor) = 1 & (-1) = 1. Partition nums by bit 1: group1 (bit set): 5, group2 (bit not set): 2,4,2. XOR group1 = 5, XOR group2 = 4.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches unique elements [OK]

Hint: Rightmost set bit partitions unique numbers correctly [OK]

Common Mistakes:

• Mixing order of output
• Incorrect xor calculation
• Miscomputing set bit

3. The following code attempts to find the single number in an array using XOR. Identify the line containing the subtle bug that causes incorrect results.

medium

A. Line 2: Initializing result to nums[0] instead of 0

B. Line 4: Returning result without sorting

C. Line 3: Looping over nums including the first element again

D. Line 1: Function definition

Solution

1. Step 1: Analyze initialization of result

   Result initialized to nums[0], then XORed again with nums[0] in loop, cancelling it out incorrectly.

2. Step 2: Understand correct initialization

   Result should start at 0 so XOR accumulates all elements exactly once.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initializing to zero avoids double XOR of first element [OK]

Hint: XOR accumulator must start at zero [OK]

Common Mistakes:

• Initializing with first element causes double XOR
• Loop includes first element again
• Misplaced return statement

4. Suppose the problem is extended to find the bitwise AND of all numbers in the range [left, right], but now left and right can be negative integers. Which modification to the optimal algorithm is necessary?

hard

A. Convert negative numbers to their 2's complement positive equivalents and then apply the algorithm.

B. Use a mask to limit the bit-length and shift both numbers until equal, considering sign bits.

C. No modification needed; the existing bit-clearing approach works for negative numbers.

D. Iterate through the entire range because bitwise AND with negatives is undefined.

Solution

1. Step 1: Understand negative number representation

   Negative integers use 2's complement, so sign bits affect bitwise AND results.

2. Step 2: Modify approach

   Masking to limit bit-length and shifting both numbers until equal handles sign bits correctly and finds common prefix.

3. Step 3: Reject naive iteration

   Iterating entire range is inefficient and unnecessary; direct bitwise manipulation with sign awareness is needed.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Handling sign bits requires masking and shifting, not naive bit-clearing [OK]

Hint: Handle sign bits with masking and shifting for negatives [OK]

Common Mistakes:

• Assuming algorithm works unchanged for negatives
• Trying to convert negatives to positives incorrectly
• Iterating entire range for negatives

5. Suppose the problem changes: you want to find the maximum product of word lengths where words can be reused multiple times (i.e., pairs can be the same word twice if allowed). Which modification to the optimal bitmasking approach correctly handles this variant?

hard

A. Precompute bitmasks and lengths, then for each word, consider its square length if it has no repeated characters, else zero; finally, check pairs as before including identical indices.

B. Remove the pruning condition and check all pairs including identical indices without overlap check.

C. Allow i and j to be equal in the nested loops and check bitmask overlap as before.

D. Use a frequency map of words and multiply lengths by frequency to find maximum product.

Solution

1. Step 1: Understand reuse of words

   Reusing the same word twice is only valid if the word has no repeated characters (so no overlap with itself).

2. Step 2: Modify approach

   Precompute bitmasks and lengths; for each word, consider its length squared if it has unique characters (bitmask check for duplicates). Then check pairs including identical indices.

3. Step 3: Why other options fail

   Allowing i=j without checking duplicates or removing pruning leads to incorrect or inefficient results; frequency map is irrelevant here.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Considering squares for unique words and pairs covers reuse correctly [OK]

Hint: Reuse allowed only if word has unique chars [OK]

Common Mistakes:

• Allowing reuse without checking duplicates in word
• Removing pruning causing inefficiency
• Using frequency maps which don't apply here