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 one at a time takes O(n log n), because a number up to n has about log2 n binary digits. Both use O(1) memory beyond the output array.

Q: Why does bits[i] = bits[i >> 1] + (i & 1) work?

i >> 1 is i with its last binary digit removed, and i & 1 is that removed digit. The 1s of i are the 1s of the shorter number plus the last digit. For 11, which is 1011 , the shorter number is 5 ( 101 , two 1s) and the last digit is 1, so 11 has three.

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. It is as fast as the shift rule and uses the same left to right fill.

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

Most languages have one, such as Integer.bitCount in Java or __builtin_popcount in C and C++, and calling it for every number gives a correct answer. Interviewers usually ask for the version without it, because the point of the problem is reusing answers you already computed. The recurrence also works in languages without such a function.

EasyBit manipulation Dynamic programming

+10

You get a whole number n that is 0 or more. For every number i from 0 to n, count how many 1s appear when i is written in binary. Return the counts as an array of n+1 entries, where entry i is the count for the number i.

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. That is 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, while 4 is 100 with a single 1. With 0, 1 and 2 from the first example, the counts for 0 to 5 are 0, 1, 1, 2, 1, 2.

+15 hidden tests on Submit

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 the 1s of every number on its own works, but it repeats work. 13 is 1101 and 6 is 110: the bits of 13 are the bits of 6 with one more digit on the end. If you fill the answers in increasing order, the count you need for i is already in the array, and each entry costs one addition.

Count each number's bits

Intuition

Take each number from 0 to n and count its 1 bits directly. The lowest bit of x is x & 1. Add it to a counter, then shift x right with x >> 1 so the next bit becomes the lowest. Stop when x reaches 0.

For 13, which is 1101, the bits come out as 1, 0, 1, 1 from the right, so the count is 3. Each number costs one step per binary digit, and a number up to n has about log2 n digits.

That makes the whole run O(n log n). For n = 2 × 10^4 it is about 20,000 × 15 = 300,000 steps, which runs in time. It still throws work away: counting 13 repeats every step you already did for 6. The space is O(1) apart from the output array.

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. So i has exactly the 1 bits of i >> 1, plus one more when its last digit is 1. That last digit is i & 1, which gives the rule bits[i] = bits[i >> 1] + (i & 1).

For every i of 1 or more, i >> 1 is smaller than i. If you fill the array from left to right, starting with bits[0] = 0, the entry you look up is always filled already. This is dynamic programming: each answer is built from a smaller one.

For n = 5: bits[1] = bits[0] + 1 = 1, bits[2] = bits[1] + 0 = 1, 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, so the time is O(n) and no memory is needed 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

The rule fits on one line, so the bugs hide around it.

The array has n+1 entries, not n. For n = 0 the answer is [0]: one entry, for the number 0.
Operator precedence. In Python, C, Java and JavaScript, + binds tighter than &, so bits[i >> 1] + i & 1 is read as (bits[i >> 1] + i) & 1. Keep the parentheses around (i & 1).
Looking up bits[i-1] instead of bits[i >> 1]. Neighbors 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 is at index floor(i/2) + 1. The runner's Lua has no shift operator, so halve with math.floor(i / 2).
Turning each number into a binary string and counting the 1 characters gives the right answer, but builds a new string for every number.

Frequently asked questions4

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 one at a time takes O(n log n), because a number up to n has about log2 n binary digits. Both use O(1) memory beyond the output array.

Why does bits[i] = bits[i >> 1] + (i & 1) work?

i >> 1 is i with its last binary digit removed, and i & 1 is that removed digit. The 1s of i are the 1s of the shorter number plus the last digit. For 11, which is 1011, the shorter number is 5 (101, two 1s) and the last digit is 1, so 11 has three.

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. It is as fast as the shift rule and uses the same left to right fill.

Can I use a built-in popcount function?

Most languages have one, such as Integer.bitCount in Java or __builtin_popcount in C and C++, and calling it for every number gives a correct answer. Interviewers usually ask for the version without it, because the point of the problem is reusing answers you already computed. The recurrence also works in languages without such a function.