Problem Description
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.
Key Insights
- The problem requires counting the number of 1's in the binary representation of each integer from 0 to n.
- A naive approach would involve converting each integer to its binary form and counting the 1's, which would lead to O(n log n) time complexity.
- A more efficient approach leverages the relationship between numbers and their binary representations, using previously computed results to find the count for the current number.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Solution
The solution uses dynamic programming to store the count of 1's for each integer in an array. For each integer i, the number of 1's can be derived from the number of 1's in i // 2 (i shifted right by one) plus the least significant bit (i & 1). This allows us to build the solution in a single pass while storing results in an array.