338. Counting Bits – Leetcode Solutions

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

class Solution:
    def countBits(self, n: int) -> List[int]:
        # Initialize an array of size n + 1 to store the number of 1's for each i
        ans = [0] * (n + 1)
        
        # Iterate from 1 to n to compute the number of 1's in the binary representation
        for i in range(1, n + 1):
            # ans[i >> 1] gives the result for i // 2, we add 1 if i is odd
            ans[i] = ans[i >> 1] + (i & 1)  # i & 1 checks if the last bit is 1 (odd number)
        
        return ans

class Solution {
public:
    vector<int> countBits(int n) {
        // Initialize a vector 'ans' of size n + 1 to store the result
        vector<int> ans(n + 1, 0);
        
        // Loop over each number from 1 to n
        for (int i = 1; i <= n; ++i) {
            // The number of 1's in i is the number of 1's in i/2 (i >> 1) plus i % 2 (i & 1)
            ans[i] = ans[i >> 1] + (i & 1);
        }
        
        // Return the result array
        return ans;
    }
};

var countBits = function(n) {
    // Create an array 'ans' of length n + 1 to store the result.
    // Initially, all elements are set to 0.
    const ans = new Array(n + 1).fill(0);

    // Iterate from 1 to n, filling in the 'ans' array.
    for (let i = 1; i <= n; i++) {
        // The number of 1's in the binary representation of 'i' can be derived
        // using the value for 'i >> 1' (which is 'i' divided by 2).
        // We add 1 to this value if 'i' is odd (i.e., 'i & 1' equals 1).
        ans[i] = ans[i >> 1] + (i & 1);
    }

    // Return the resulting array 'ans' that contains the number of 1's in the binary representation for each number.
    return ans;
};

class Solution {
    // Function to count the number of 1's in binary representation of numbers from 0 to n
    public int[] countBits(int n) {
        // Array to store the result (number of 1's for each number from 0 to n)
        int[] ans = new int[n + 1];
        
        // Start from 0 up to n
        for (int i = 1; i <= n; i++) {
            // If i is even, the number of 1's is the same as the number of 1's in i / 2
            // If i is odd, it's the same as i / 2 but with an additional 1 (because of the least significant bit)
            ans[i] = ans[i >> 1] + (i & 1);
        }
        
        // Return the array containing the result for each number
        return ans;
    }
}