LeetCode 338: Counting Bits

Explanation

We can solve this problem using dynamic programming. For any number i, the number of set bits in i can be determined by adding 1 to the count of set bits in i/2 if i is odd, and taking the count of set bits in i/2 if i is even. We can build the result array iteratively based on this logic.

• Time complexity: O(n)
• Space complexity: O(n)

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n+1];
        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
}