Counting BitsEasy

Counting Bits

Easy 9.7k76% acceptance

Dynamic ProgrammingBit Manipulation

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary representation of i, for every i from 0 to n.

Example 1

Input: n = 2

Output: [0,1,1]

0 → 0 bits, 1 → 1 bit, 2 (10) → 1 bit.

Example 2

Input: n = 5

Output: [0,1,1,2,1,2]

0,1,10,11,100,101 have 0,1,1,2,1,2 set bits.

Constraints

0 ≤ n ≤ 10⁵

Asked atAmazonAppleGoogle

JavaScript

⌘↵ to run

Loading editor…

Case 1

0

expected: [0]

Case 2

1

expected: [0,1]

Case 3

2

expected: [0,1,1]

Case 4

5

expected: [0,1,1,2,1,2]

Case 5

8

expected: [0,1,1,2,1,2,2,3,1]

Case 6

10

expected: [0,1,1,2,1,2,2,3,1,2,2]