Loading problem...
Given a non-negative integer n, your task is to construct and return an array result of length n + 1 where each element result[i] represents the count of set bits (binary digits equal to 1) in the binary representation of the number i.
In computing, the number of 1-bits in a binary number is often called its population count or Hamming weight. For example, the number 5 in binary is 101, which contains two 1-bits, so its population count is 2.
Your solution should efficiently compute the population count for every integer from 0 to n (inclusive) and return these counts as an array. The challenge lies in finding an approach that avoids recomputing the bit count from scratch for each number, instead leveraging patterns and relationships between consecutive numbers.
n = 2[0,1,1]For each number from 0 to 2: • 0 in binary is '0' → 0 ones • 1 in binary is '1' → 1 one • 2 in binary is '10' → 1 one Thus, the result array is [0, 1, 1].
n = 5[0,1,1,2,1,2]For each number from 0 to 5: • 0 → '0' → 0 ones • 1 → '1' → 1 one • 2 → '10' → 1 one • 3 → '11' → 2 ones • 4 → '100' → 1 one • 5 → '101' → 2 ones Thus, the result array is [0, 1, 1, 2, 1, 2].
n = 10[0,1,1,2,1,2,2,3,1,2,2]The pattern continues for numbers 0 through 10: • Numbers 6 ('110') and 7 ('111') have 2 and 3 ones respectively • 8 ('1000') resets to 1 one, then 9 ('1001') and 10 ('1010') each have 2 ones The complete result is [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2].
Constraints