Counting Bits

The problem

You are given a whole number limit. For every number i from 0 to limit, count the 1 bits in the binary form of i. Return the n + 1 counts as an array, where entry i is the count for i.

Example 1

Input: limit = 7

Output: [0, 1, 1, 2, 1, 2, 2, 3]

For example, 5 is 101, so entry 5 is 2. And 7 is 111, so entry 7 is 3.

bit_counts

0011122314252637

Example 2

Input: limit = 2

Output: [0, 1, 1]

0 has no 1 bits. 1 is 1 and 2 is 10, so each has one.

Example 3

Input: limit = 0

Output: [0]

Only the number 0, which has no 1 bits.

Constraints

• 0 ≤ limit ≤ 100,000. Below, n is limit.

Clarifying questions

Is 0 included?

Yes. The array has n + 1 entries, from 0 to n.

Does the output array count as extra memory?

No. We must return it anyway, so we only count memory on top of it.

Can we use a built-in bit count?

It works, but the follow-up asks for one pass in O(n) without it.

Spot the pattern

We need an answer for every number up to limit, and each number is close to a smaller one: i >> 1 is i with its last bit dropped. Building each answer from a smaller answer we already have is dynamic programming.

Solutions

Count each numberO(n log n)Reuse i >> 1O(n)

Show all

This problem has two approaches. A third one, using i & (i − 1), is also O(n) and works the same way.

Count each number O(n log n)

The idea

For each i from 0 to limit, count its 1 bits on its own. Copy i into remaining and remove its lowest 1 bit with remaining & (remaining − 1) until remaining is 0. The number of runs is the count.

It is correct, but each number starts from scratch, even though 6 (110) is just 3 (11) with a 0 added.

Walkthrough

bit_counts

0001020304050607

1. bit_counts = [0] * (limit + 1)
2. for i in range(limit + 1):
3. remaining = i
4. while remaining:
5. remaining &= remaining - 1
6. bit_counts[i] += 1
7. return bit_counts

For each i from 0 to 7, count its 1 bits on its own with the n & (n − 1) loop.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Count each number: remove the lowest 1 bit of i until it is 0.
    // Up to log n + 1 runs for each of n + 1 numbers: O(n log n) time, O(1) extra memory.
    public int[] countBits(int limit) {
        int[] bitCounts = new int[limit + 1];
        for (int i = 0; i <= limit; i++) {
            int remaining = i;
            while (remaining != 0) {
                // remaining & (remaining - 1) is remaining with its lowest 1 bit removed.
                remaining &= remaining - 1;
                bitCounts[i]++;
            }
        }
        return bitCounts;
    }
}

Big O

Time O(n log n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines remove one 1 bit and add 1 to the count. That is 1 step. They sit inside two loops: the outer one picks i, and the inner one runs once per 1 bit of i.

   1. bit_counts = [0] * (limit + 1)
   2. for i in range(limit + 1):
   3. remaining = i
   4. while remaining:
   5. remaining &= remaining - 1
   6. bit_counts[i] += 1
   7. return bit_counts

2. 2 Count the runs on Example 1

   Example 1 has n = 7. The table shows the inner runs for each i, which is its number of 1 bits.

   0 + 1 + 1 + 2 + 1 + 2 + 2 + 3 = 12 inner runs, plus 8 runs of the outer loop.

   i	0	1	2	3	4	5	6	7
   inner runs	0	1	1	2	1	2	2	3

   total

   0 + 1 + 1 + 2 + 1 + 2 + 2 + 3 = 12 inner runs, plus 8 outer runs

3. 3 Write the count for any n

   A number up to limit has about log₂ n + 1 bits, so it has at most that many 1 bits. There are n + 1 numbers:

   at most (n + 1) × (log₂ n + 1) inner runs

   Check it with Example 1: 8 × 3 = 24, and the real count is 12. On average only half the bits are 1.

4. 4 Keep only the part that grows fastest

   • Drop the +1s. They are small next to n and log n.

   What is left is n log n. Half of the bits being 1 on average only halves the count, so it stays n log n.

   So the time is O(n log n).

5. S Space: count the extra memory the same way

   Besides the output, the code keeps i and remaining. The extra space is O(1).

   bit_counts (the output)iremaining

Reuse i >> 1 O(n)

The idea

Shifting i right by one, i >> 1, drops its last bit. Every other bit stays a bit. So:

bit_counts[i] = bit_counts[i >> 1] + (i & 1)

i >> 1 is smaller than i, so its answer is already in the array when we reach i. Fill the array from 1 up to limit, starting from bit_counts[0] = 0.

Walkthrough

bit_counts

0001020304050607

1. bit_counts = [0] * (limit + 1)
2. for i in range(1, limit + 1):
3. bit_counts[i] = bit_counts[i >> 1] + (i & 1)
4. return bit_counts

Shifting i right by one drops its last bit. So i has the 1 bits of i >> 1, plus 1 if its last bit is 1. bit_counts[0] = 0 to start.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Reuse i >> 1: it is i without its last bit, and its answer is already known.
    // One lookup per number: O(n) time, O(1) extra memory.
    public int[] countBits(int limit) {
        int[] bitCounts = new int[limit + 1];
        for (int i = 1; i <= limit; i++) {
            // Keep the parentheses: in most languages + binds tighter than &.
            bitCounts[i] = bitCounts[i >> 1] + (i & 1);
        }
        return bitCounts;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line does one array read, one shift, one & and one add. That is 1 step. It sits inside one loop.

   1. bit_counts = [0] * (limit + 1)
   2. for i in range(1, limit + 1):
   3. bit_counts[i] = bit_counts[i >> 1] + (i & 1)
   4. return bit_counts

2. 2 Count the runs on Example 1

   Example 1 has n = 7. The loop runs for i = 1 to 7. The table shows which entry each run reads and what it adds.

   7 runs.

   i	1	2	3	4	5	6	7
   reads bit_counts[…]	0	1	1	2	2	3	3
   adds	1	0	1	0	1	0	1

   total

   7 runs

3. 3 Write the count for any n

   The loop runs once per number from 1 to limit:

   n runs

   Check it with Example 1: n = 7, 7 runs, against 12 inner runs for counting each number.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is already n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   Besides the output, the code keeps only i. The extra space is O(1).

   bit_counts (the output)i

Common mistake

Missing parentheses around i & 1

In Python, Java, C# and TypeScript, + binds tighter than &. So bit_counts[i >> 1] + i & 1 means (bit_counts[i >> 1] + i) & 1, which is wrong. Write bit_counts[i >> 1] + (i & 1).

Tested at the limits

2,000 random limits from 0 to 70, which cover 0, 1 and the powers of two where the count drops back to 1. Count each number and reuse i >> 1 gave the same answer every time.

Largest inputs	Result
limit = 100,000 (the most allowed). Reuse i >> 1.	0.004 s, and about 0.8 MB, all of it the answer list of 100,001 counts. Nothing else grows.
limit = 100,000. Count each number.	0.05 s, about 10 times slower: it counts up to 17 bits for each number.