Counting Bits

Given a non-negative integer n, return an array ans where ans[i] is the number of set bits in i for every i in [0, n]. Pattern focus: Clear Lowest Bit. Build the answer incrementally while reusing previously computed values.

Input Format

n = upper bound integer

Output Format

set-bit counts from 0 to n

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • n must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

n = 5

Output:

[0,1,1,2,1,2]

Explanation:

The counts from 0 to 5 are 0, 1, 1, 2, 1, and 2.

Example 2:

Input:

n = 1

Output:

[0,1]

Explanation:

The sequence starts with 0 and 1.

Loading...
Counting Bits - Bit Manipulation DSA Problem