Counting Bits — Easy Coding Interview Question

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

Input: n = 2

Output: [0,1,1]

Constraints

• 0 ≤ n ≤ 10⁵

Topics & Companies

Topics: bit-manipulation, dp

Asked by: Amazon, Google, Meta, Microsoft

Optimal Solution Complexity

Time complexity: O(n). Space complexity: O(n).

Practice more

• All DSA Problems
• DSA Patterns