Counting Bits

bit-manipulationdynamic-programming

Problem

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1s in the binary representation of i, for every i from 0 to n.

Examples

Example 1

Input: n = 2

Output: [0,1,1]

Explanation: 0 -> 0, 1 -> 1, 2 (binary 10) -> 1

Example 2

Input: n = 5

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

Explanation: 5 = 101 in binary -> 2 set bits

Constraints

•0 <= n <= 10^5

Hints

Hint 1

The brute force counts each number's bits independently (e.g. via Brian Kernighan's n &= (n-1) trick, repeated until n is 0) — correct, but redundant work across nearby numbers.

Hint 2

Can the answer for i be built from the answer for some SMALLER number you've already computed, instead of counting from scratch?

Hint 3

i >> 1 drops i's lowest bit — ans[i >> 1] already has the count for everything else; add back 1 if that dropped bit was itself a 1 (i.e. i is odd).

Solutions

public int[] countBitsBruteForce(int n) {
    int[] ans = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int num = i, count = 0;
        while (num != 0) {
            num &= (num - 1); // clears the lowest set bit
            count++;
        }
        ans[i] = count;
    }
    return ans;
}

Time: O(n log(max n)) · Space: O(n) for output, O(1) extra