Counting Bits (0 to N)

📋

Problem

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.

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

Edge cases: n = 0 → [0]n = 1 → [0,1]n = 2 → [0,1,1]

</>

IDE

def countBits(n: int) -> list:public int[] countBits(int n)vector<int> countBits(int n)function countBits(n)

def countBits(n):
    # Write your solution here
    pass

class Solution {
    public int[] countBits(int n) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> countBits(int n) {
    // Write your solution here
    return {};
}

function countBits(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [0,1,1,1,1,2]Greedy approach subtracting largest power of two but not counting bits correctly.✅ Use dp[i] = dp[i >> 1] + (i & 1) instead of greedy subtraction.

Wrong: [0]Fails to handle n > 0, returns only dp[0].✅ Initialize dp array of size n+1 and fill all values up to n.

Wrong: [0,1,1]Off-by-one error causing missing last element for n=2.✅ Loop from 0 to n inclusive and return dp of length n+1.

Wrong: Timeout or no outputBrute force bit counting for each number causing O(n log n) time complexity.✅ Use O(n) DP approach with dp[i] = dp[i >> 1] + (i & 1).

✓

Test Cases

Try testing your solution on boundary inputs like n=0 and n=1 to ensure correctness.

Consider tricky inputs that expose greedy or off-by-one errors; test powers of two and small ranges.

Optimize your solution to O(n) time using DP with bit shifts to handle large inputs efficiently.

t1_01basic

Input{"n":5}

Expected[0,1,1,2,1,2]

⏱ Performance - must finish in 2000ms

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

💡 Think about how to count bits for each number from 0 to n.

💡 Use dynamic programming or bit manipulation to avoid repeated counting.

💡 Use dp[i] = dp[i >> 1] + (i & 1) to build results efficiently.

Why it failed: Output incorrect for canonical example; likely not counting bits correctly or off-by-one indexing. Fix by using dp[i] = dp[i >> 1] + (i & 1).

✓ Correctly counts bits for all numbers up to n.

t1_02basic

Input{"n":3}

Expected[0,1,1,2]

⏱ Performance - must finish in 2000ms

Binary: 0(0),1(1),2(10),3(11). Counts of 1 bits are [0,1,1,2].

💡 Try enumerating bits for small n to verify correctness.

💡 Check if your solution handles small inputs without errors.

💡 Confirm dp or bit counting logic works for n=3.

Why it failed: Incorrect output for small input n=3; possibly indexing or initialization error. Fix by initializing dp array with dp[0]=0 and building up.

✓ Correctly handles small inputs and counts bits.

t2_01edge

Input{"n":0}

Expected[0]

⏱ Performance - must finish in 2000ms

Only number 0, which has 0 set bits.

💡 Check behavior when n is zero.

💡 Make sure your code handles the smallest input without errors.

💡 Return [0] directly or ensure dp array includes index 0.

Why it failed: Fails on n=0 by returning empty or invalid array; fix by initializing dp with dp[0]=0 and returning dp.

✓ Correctly returns [0] for n=0.

t2_02edge

Input{"n":1}

Expected[0,1]

⏱ Performance - must finish in 2000ms

Numbers 0 and 1 have 0 and 1 set bits respectively.

💡 Test single element beyond zero.

💡 Check if your code correctly counts bits for 1.

💡 Confirm dp[1] = dp[0] + 1 = 1 or equivalent logic.

Why it failed: Incorrect output for n=1; likely off-by-one or missing dp initialization. Fix by ensuring dp array size n+1 and correct recurrence.

✓ Correctly counts bits for n=1.

t2_03edge

Input{"n":2}

Expected[0,1,1]

⏱ Performance - must finish in 2000ms

Numbers 0,1,2 have bit counts 0,1,1 respectively.

💡 Check exact boundary conditions at n=2.

💡 Verify dp or bit counting logic for small boundary inputs.

💡 Use dp[i] = dp[i >> 1] + (i & 1) to handle this correctly.

Why it failed: Fails at boundary n=2; possibly incorrect loop bounds or indexing. Fix by looping from 0 to n inclusive.

✓ Handles exact boundary n=2 correctly.

t3_01corner

Input{"n":7}

Expected[0,1,1,2,1,2,2,3]

⏱ Performance - must finish in 2000ms

Binary 0 to 7: counts of 1 bits are as shown.

💡 Beware of greedy approaches that count bits incorrectly.

💡 Check if your solution counts bits independently for each number or uses dp.

💡 Use dp[i] = dp[i >> 1] + (i & 1) instead of greedy subtraction.

Why it failed: Fails greedy trap by incorrectly counting bits (e.g., subtracting largest power of two). Fix by using dp with right shift and bitwise AND.

✓ Avoids greedy trap and counts bits correctly.

t3_02corner

Input{"n":8}

Expected[0,1,1,2,1,2,2,3,1]

⏱ Performance - must finish in 2000ms

Binary 0 to 8: counts of 1 bits including exact power of two boundary.

💡 Check handling of exact powers of two like 8 (1000).

💡 Verify dp recurrence handles exact boundaries correctly.

💡 dp[i] = dp[i >> 1] + (i & 1) works for powers of two.

Why it failed: Fails exact boundary test by miscounting bits for powers of two. Fix by ensuring dp recurrence uses right shift and bitwise AND.

✓ Correctly counts bits at exact power of two boundaries.

t3_03corner

Input{"n":15}

Expected[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]

⏱ Performance - must finish in 2000ms

Binary 0 to 15: counts of 1 bits for all 4-bit numbers.

💡 Beware off-by-one errors in loops or indexing.

💡 Check if your solution includes all numbers up to n inclusive.

💡 Ensure dp array size is n+1 and loop runs i in [0,n].

Why it failed: Off-by-one error causes missing or extra elements. Fix by looping from 0 to n inclusive and returning dp of length n+1.

✓ Handles full range correctly without off-by-one errors.

t4_01performance

Input{"n":100000}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000 tests O(n) DP solution performance; brute force O(n log n) may time out.

💡 Use O(n) dynamic programming approach with dp[i] = dp[i >> 1] + (i & 1).

💡 Avoid counting bits individually for each number (O(n log n)).

💡 Precompute results in a single pass to meet time constraints.

Why it failed: TLE due to O(n log n) brute force bit counting. Fix by using O(n) DP with right shift and bitwise AND.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Given the following Python code, what is the output of isPowerOfFour(16)?

easy

A. True

B. False

C. Raises an error due to floating point precision

D. None

Solution

1. Step 1: Calculate log2(16)

   log2(16) = 4, dividing by 2 gives 2.0.

2. Step 2: Check if 2.0 equals int(2.0)

   2.0 == 2 is True, so the function returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   16 is 4^2, so output True is expected [OK]

Hint: log2(16)/2 = 2.0 equals int(2) -> True

Common Mistakes:

• Assuming floating point error causes failure
• Confusing power of two with power of four

2. What is the time complexity of generating an n-bit Gray code sequence using the optimal bitwise formula [i ^ (i >> 1) for i in range(1 << n)]?

medium

A. O(n)

B. O((2^n)!)

C. O(n * 2^n)

D. O(2^n)

Solution

1. Step 1: Analyze the loop iteration count

   The list comprehension iterates over all integers from 0 to 2^n - 1, so 2^n iterations.

2. Step 2: Analyze work per iteration

   Each iteration performs constant time bitwise operations (XOR and right shift), so O(1) per iteration.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Total time is proportional to 2^n, not multiplied by n or factorial [OK]

Hint: Loop runs 2^n times with O(1) work each [OK]

Common Mistakes:

• Confusing n with 2^n and claiming O(n)
• Assuming bitwise operations cost O(n)
• Mistaking factorial complexity from brute force backtracking

3. Consider this buggy code snippet for finding two unique numbers. Which line contains the subtle bug?

medium

A. Line 8: set_bit calculation

B. Line 6: xor calculation loop

C. Line 3: xor initialization

D. Line 12: partitioning condition

Solution

1. Step 1: Identify how set_bit is computed

   Correct approach uses set_bit = xor & (-xor) to isolate rightmost set bit. Here, set_bit = xor misses this step.

2. Step 2: Understand impact of bug

   Without isolating rightmost set bit, partitioning fails, XOR groups won't separate unique numbers correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bug in set_bit calculation breaks partitioning [OK]

Hint: Isolate rightmost set bit with xor & (-xor) [OK]

Common Mistakes:

• Using xor directly as set_bit
• Breaking early before full XOR
• Misusing partition condition

4. 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

5. If the input array can contain negative numbers, which modification is necessary for the optimal XOR and partition approach to correctly find the two unique numbers?

hard

A. No modification needed; the current approach works for negative numbers as is.

B. Use absolute values of numbers for XOR and partitioning to avoid sign issues.

C. Sort the array first to handle negative numbers before applying XOR partitioning.

D. Use set_bit = xor & (-xor) carefully, ensuring two's complement representation is handled correctly.

Solution

1. Step 1: Understand bitwise operations with negative numbers

   Negative numbers use two's complement; -xor computes two's complement correctly, so set_bit = xor & (-xor) works if implemented carefully.

2. Step 2: Identify necessary care

   Ensure language and environment handle negative bitwise operations properly; no need to sort or use absolute values.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct handling of two's complement is key for negative numbers [OK]

Hint: Two's complement handles negative bits; no sorting needed [OK]

Common Mistakes:

• Assuming XOR fails on negatives
• Sorting wastes time
• Using absolute values breaks uniqueness