LeetCode 338 · Bit Manipulation

Counting Bits, explained with a picture

Each number borrows its count from its half.

EasyBit Manipulation
▶ Watch it step by step

The problem

For every number from 0 to n, count the 1 bits in its binary form. Return the list of counts.

Input:  n = 8
Output: [0, 1, 1, 2, 1, 2, 2, 3, 1]

Picture it

Picture each number as a switch panel. Shifting a number right by one (halving it) just drops its last switch. So the count for i = the count for i ÷ 2 (already computed) + the last switch (i is odd → 1).

How to recognise it

  • You need an answer for every number from 0 to n, not just one.
  • The answer for i can be built from the answer for a smaller number you have already computed: that is dynamic programming (DP: store answers to small cases and reuse them).
  • Shifting right by one (i >> 1, the same as i // 2) drops the last bit, so i and i // 2 share all bits except one.
  • n is up to 10^5, and the follow-up asks for O(n) time with no built-in popcount.

Start with brute force

Count the 1 bits of each number separately, one bit at a time.

def count_bits_brute(n):
    ans = []
    for i in range(n + 1):
        c, x = 0, i
        while x:
            c += x & 1
            x >>= 1
        ans.append(c)
    return ans

Each number takes as many steps as it has bits, about log2(i), so the total is O(n log n): roughly 1.7 × 10^6 steps for n = 10^5. That passes, but it ignores that every number repeats the work already done for a smaller one.

From brute force to the idea

  1. Find the waste. Counting the bits of 13 (1101) re-counts the bits of 6 (110), which was finished seven numbers earlier.
  2. Split off the last bit. i >> 1 is i without its last bit, and i & 1 is that last bit (1 if i is odd). So the 1 bits of i are the 1 bits of i >> 1 plus i & 1.
  3. Fill the table in order. i >> 1 is smaller than i for every i ≥ 1, so ans[i >> 1] is always ready when i is reached.
  4. Start from the base case. ans[0] = 0, already set by [0] * (n + 1).

This is the key idea: ans[i] = ans[i >> 1] + (i & 1), one O(1) step per number.

Another valid recurrence is ans[i] = ans[i & (i - 1)] + 1, which uses the "clear the lowest 1 bit" trick from Number of 1 Bits.

The key idea

bits[i] = bits[i >> 1] + (i & 1). O(n).

Python solution

def count_bits(n):
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        ans[i] = ans[i >> 1] + (i & 1)   # i = (i // 2) shifted, plus last bit
    return ans

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (count each)O(n log n): about log2(i) steps per numberO(1) besides the output
DP on i >> 1 (shown code)O(n): one lookup and one addition per numberO(1) besides the output list of n + 1 counts

Edge cases

  • n = 0: returns [0]; the loop never runs.
  • Powers of two (1, 2, 4, 8): each has count 1, because i >> 1 is the previous power of two and i & 1 is 0.
  • All ones (7 = 111): ans[3] + 1 = 3.
  • n = 10^5: a list of 100,001 small integers, no problem.

Common mistakes

  • Writing ans[i >> 1] + 1, which forgets that the dropped bit may be 0: 2 (binary 10) then gets 2 instead of 1.
  • Writing ans[i] = ans[i - 1] + 1, which only holds when i − 1 is even.
  • Starting the loop at 0 and computing ans[0] from ans[0]: harmless here, but a sign of not thinking about the base case.
  • Precedence: ans[i >> 1] + i & 1 means (ans[i >> 1] + i) & 1; keep the brackets around i & 1.
Your turn: parity of every number

Return, for each i from 0 to n, 1 if i has an odd number of 1 bits and 0 if even. For n = 8 the answer is [0, 1, 1, 0, 1, 0, 0, 1, 1]. Do it in O(n). Describe your approach, then write it if you like.

Compare with our answer

Same split: the parity of i is the parity of i >> 1, flipped if the last bit is 1. Flipping a 0/1 value is XOR with 1, so XOR replaces the addition.

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

Time O(n), and the output takes O(n) space.

A strong answer mentions: reusing ans[i >> 1], that adding a bit and keeping only odd/even is XOR, and the base case ans[0] = 0.

Check what stuck

1. You must output, for every i from 0 to n, the position of its highest 1 bit (0 for i = 1). Which approach fits best?

2. Why is ans[i >> 1] always available when the loop reaches i?

3. A learner writes ans[i] = ans[i >> 1] + 1. What is the first value of i where the list is wrong?

Score 60% or more and the lesson is marked complete.