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’s in the binary representation of i.

Example 1:

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

Constraints:

• 0 <= n <= 10^5

ans[i] = ans[i >> 1] + (i & 1) using dynamic programming.

Bit Manipulation DP

graph TD
    A["Input Integer / Bits"] --> B["Apply Bitwise Operation (AND / XOR / Shift)"]
    B --> C{"Check Bit Condition"}
    C -- "Condition Met" --> D["Update Bit Count / Result"]
    C -- "Continue" --> E["Shift Bits (>>> 1 or & n-1)"]
    E --> B
    D --> F["Return Final Result"]

function countBits(n) {
  const ans = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    ans[i] = ans[i >> 1] + (i & 1);
  }
  return ans;
}

• Time Complexity: O(n)
• Space Complexity: O(n)
• Explanation: O(n) DP bit relation.

function countBits(n) {
  const ans = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    ans[i] = ans[i >> 1] + (i & 1);
  }
  return ans;
}

• Time Complexity: O(n)
• Space Complexity: O(n)
• Explanation: O(n) DP bit relation.

1. Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
2. Iterate & Evaluate: Process the input according to the boundary conditions.
3. Update & Return: Compute the optimal answer and return early or at termination.

Number of bits for i equals bits for i >> 1 plus i % 2.

1. Use previous DP values for i >> 1.

👉 Solve this problem interactively in the DSA Lab