Bit Manipulation - Counting Bits

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.

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

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Explanation: 0→0, 1→1, 2→1, 3→2, 4→1, 5→2.

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).

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.