Count Bits Explained

Problem Statement

Given a non-negative integer n, return an array ans of length n + 1, where ans[i] represents the number of 1 bits in the binary representation of i for 0 <= i <= n. This problem tests your ability to compute Hamming weights efficiently for a range of numbers, often using dynamic programming or bit manipulation to exploit patterns.

Example

Input: n = 5

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

Explanation: 0 = 000 (0 bits), 1 = 001 (1 bit), 2 = 010 (1 bit), 3 = 011 (2 bits), 4 = 100 (1 bit), 5 = 101 (2 bits).

Code

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(Arrays.toString(sol.countBits(5))); // [0, 1, 1, 2, 1, 2]
    }
}
            

def count_bits(n):
    ans = [0] * (n + 1)
    for i in range(n + 1):
        ans[i] = ans[i >> 1] + (i & 1)
    return ans

# Example usage
print(count_bits(5))  # [0, 1, 1, 2, 1, 2]
            

function countBits(n) {
    const ans = new Array(n + 1).fill(0);
    for (let i = 0; i <= n; i++) {
        ans[i] = ans[i >> 1] + (i & 1);
    }
    return ans;
}

// Example usage
console.log(countBits(5)); // [0, 1, 1, 2, 1, 2]
            

Explanation

• Initialize an array ans of size n + 1 with zeros.
• For each i from 0 to n:
• Compute the number of 1 bits in i >> 1 (i.e., i/2), stored in ans[i >> 1].
• Add the least significant bit of i using i & 1.
• Store the sum in ans[i].
• Return the array ans.

Note