Counting Bits

Share

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1-bits in the binary representation of i.

Example 1
Input: n = 2
Output: [0, 1, 1]
Explanation: 0 → 0 bits, 1 → 1 bit, 2 (10) → 1 bit.
Example 2
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Explanation: 0→0, 1→1, 2→1, 3→2, 4→1, 5→2.

Solution Approach

Use dynamic programming with the recurrence: bits[i] = bits[i >> 1] + (i & 1). Shifting i right by one removes the last bit (which is handled by i & 1), and bits[i >> 1] is already computed.

  • Create array dp of size n+1 with dp[0] = 0.
  • For each i from 1 to n: dp[i] = dp[i >> 1] + (i & 1).
  • i >> 1 gives i with its last bit dropped (already computed).
  • i & 1 adds 1 if i is odd (last bit is 1).
Java
class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
}
Complexity Analysis:

Time complexity: O(n). Single pass from 1 to n.
Space complexity: O(n). For the output array.