Bit Manipulation Counting and shifting bits
117. Counting Bits
You are given an integer n. Return a list answer of n + 1 integers, where answer[i] is the number of
set bits in i, for every i from 0 to n.
A set bit is a 1 in the binary form of a number. For example, 13 is 1101 in binary, so it has three set
bits.
Example 1
Input: n = 9
[0,1,1,2,1,2,2,3,1,2]Explanation: In binary, 0 to 9 are 0, 1, 10, 11, 100, 101, 110, 111, 1000 and 1001. Counting the
1s in each gives the list, so 7 has three set bits and 8 has one.
Example 2
Input: n = 0
[0]Explanation: The only number is 0, which has no set bits. The answer still holds one value.
Example 3
Input: n = 16
[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1]Explanation: 15 is 1111, so it has four set bits. The next number, 16, is 10000 and has only one.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ n ≤ 105
Clarifying questions
What you would ask an interviewer before writing any code.