Counting Bits

Easy Problem 147 of 151 Java and Python

Problem

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary representation of i.

Example 1

Input: n = 2
Output: [0, 1, 1]
Why: 0 → 0, 1 → 1, 2 → 10.

Example 2

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]

Constraints

0 ≤ n ≤ 10⁵
Follow-up: O(n) without built-in bit counting.

Explanation

i >> 1 is i with its last bit removed, and it is smaller than i, so its answer is already known. Then bits(i) = bits(i >> 1) + (i & 1).

Approach 1 · Naive

Count each number separately

Time O(n log n)
Space O(1) besides the output

Run the Number of 1 Bits loop for every i.

For each i in 0…n, count its set bits with x &= x - 1.

Java

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int x = i;
            while (x != 0) {
                x &= x - 1;
                ans[i]++;
            }
        }
        return ans;
    }
}

Python

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = []
        for i in range(n + 1):
            count, x = 0, i
            while x:
                x &= x - 1
                count += 1
            ans.append(count)
        return ans

Approach 2 · Optimal

DP on the last bit

Time O(n)
Space O(1) besides the output

Reuse the answer for i >> 1 and add the last bit.

ans[0] = 0.
For i from 1 to n: ans[i] = ans[i >> 1] + (i & 1).

Java

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
}

Python

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)
        return ans

Complexity compared

Approach	Time	Space
Naive Count each number separately	O(n log n)	O(1) besides the output
Optimal DP on the last bit	O(n)	O(1) besides the output

Key takeaways

Another valid recurrence: ans[i] = ans[i & (i - 1)] + 1 (remove the lowest set bit).

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem