Counting Bits

Q: What is the time complexity of Counting Bits?

The best solution runs in O(n) time: each of the n+1 entries comes from one earlier entry with one addition. Counting every number's bits on its own takes O(n log n). Both use O(1) memory beyond the output array.

Q: Is there another O(n) recurrence for Counting Bits?

Yes. i & (i-1) clears the lowest 1 bit of i , so bits[i] = bits[i & (i-1)] + 1 for every i of 1 or more. For 12 ( 1100 ), 12 & 11 is 8 ( 1000 ), which has one 1, so 12 has two.

Q: Can I use a built-in popcount function?

Calling one for every number, such as Integer.bitCount in Java or __builtin_popcount in C and C++, gives a correct answer. Interviewers usually ask for the version without it, because the point of the problem is reusing answers you already computed.

EasyBit manipulation Dynamic programming

+10

Given a whole number n that is 0 or more, return an array of n+1 entries where entry i is the number of 1s in the binary form of i, for every i from 0 to n.

Function

countBits(n: integer) → integer-array

ninteger: the last number to count, 0 or more
Returnsinteger-array: an array of n+1 counts, where entry i is the number of 1 bits in i

Constraints

0 ≤ n ≤ 2 × 10⁴

Examples

Input: n = 2
Output: [0, 1, 1]
Explanation: In binary, 0 is 0, 1 is 1 and 2 is 10: no 1s, then one, then one.

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Explanation: 3 is 11 and 5 is 101, two 1s each; 4 is 100, with one. With 0, 1 and 2 from the first example, the counts are 0, 1, 1, 2, 1, 2.

Follow-up

Can you fill the whole array in O(n) time, without a built-in function that counts bits and without counting each number from scratch?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Counting every number from scratch repeats work: 13 is 1101, the bits of 6 (110) with one more digit on the end. Fill the answers in increasing order and each entry reuses a smaller one with one addition.

Count each number's bits

Intuition

Count each number's 1 bits directly: add x & 1 to a counter, shift x right by one, and stop at 0. For 13 (1101) the bits come out 1, 0, 1, 1, so the count is 3.

A number up to n has about log2 n binary digits, so the run is O(n log n): about 20,000 × 15 = 300,000 steps for n = 2 × 10^4.

Algorithm

Start an empty result list.
For each i from 0 to n, set count to 0 and x to i.
While x is above 0, add x & 1 to count and shift x right by one.
Append count to the result.
Return the result.

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

Build on half the number

Intuition

Shifting i right by one deletes its last binary digit, and i & 1 is that digit. So i has the 1s of i >> 1 plus its last digit: bits[i] = bits[i >> 1] + (i & 1).

For every i of 1 or more, i >> 1 is smaller than i, so filling the array from left to right, starting at bits[0] = 0, means the entry you read is always ready. For n = 5: bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2.

Each entry is one shift, one AND and one addition: O(n) time and no memory beyond the output.

Algorithm

Create an array bits of n+1 zeros. bits[0] stays 0.
For i from 1 to n, set bits[i] to bits[i >> 1] + (i & 1).
Return bits.

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

Pitfalls and edge cases

Returning n entries instead of n+1. For n = 0 the answer is [0].
Operator precedence. In Python, C, Java and JavaScript, + binds tighter than &, so bits[i >> 1] + i & 1 means (bits[i >> 1] + i) & 1. Keep the parentheses around (i & 1).
Looking up bits[i-1] instead of bits[i >> 1]. Neighbours share no simple rule: 7 is 111 with three 1s, and 8 is 1000 with one.
In Lua and R, arrays start at 1, so the count for i sits at index i+1 and the lookup for i >> 1 at floor(i/2) + 1. Lua 5.1 has no shift operator, so halve with math.floor(i / 2).

Frequently asked questions3

What is the time complexity of Counting Bits?

The best solution runs in O(n) time: each of the n+1 entries comes from one earlier entry with one addition. Counting every number's bits on its own takes O(n log n). Both use O(1) memory beyond the output array.

Is there another O(n) recurrence for Counting Bits?

Yes. i & (i-1) clears the lowest 1 bit of i, so bits[i] = bits[i & (i-1)] + 1 for every i of 1 or more. For 12 (1100), 12 & 11 is 8 (1000), which has one 1, so 12 has two.

Can I use a built-in popcount function?

Calling one for every number, such as Integer.bitCount in Java or __builtin_popcount in C and C++, gives a correct answer. Interviewers usually ask for the version without it, because the point of the problem is reusing answers you already computed.