338. Counting Bits

Description

The problem requires generating an array of integers where each integer at index i in the array represents the number of 1 bits in the binary representation of the integer i. For example, for n = 5, the output would be [0, 1, 1, 2, 1, 2], where:

• 0 has 0 bits set to 1.
• 1 has 1 bit set to 1.
• 2 has 1 bit set to 1.
• 3 has 2 bits set to 1.
• 4 has 1 bit set to 1.
• 5 has 2 bits set to 1.

Intuition

The core idea is to efficiently count the number of 1 bits for every integer from 0 to n. Counting the number of 1 bits in the binary representation of a number can be done by either converting the number to a binary string and counting the 1 characters, or by using built-in functions that are optimized for this task.

Approach

1. Initialization: Create an array arr of size n+1 filled with zeros.
2. Iteration: Loop through each integer i from 1 to n: - Convert i to its binary form and count the number of 1 bits. - Store the result in arr[i].
3. Return: After the loop completes, the array arr will contain the number of 1 bits for each integer from 0 to n.

Optimizations:

• Instead of converting to a binary string and counting manually, use language-specific built-in functions for counting set bits, which are generally more efficient.

Complexity

Time Complexity:

O(n * log n) if converting to binary and counting bits manually, but O(n) when using built-in functions like __builtin_popcount in C++, Integer.bitCount in Java, or bin(i).count('1') in Python.

Space Complexity:

O(n) for storing the result in the array.

Code

C++

class Solution {
public:
    std::vector countBits(int n) {
        std::vector arr(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            arr[i] = __builtin_popcount(i); // Efficient way to count set bits in an integer
        }
        return arr;
    }
};

Python

class Solution:
    def countBits(self, n: int) -> list[int]:
        arr = [0] * (n + 1)
        for i in range(1, n + 1):
            arr[i] = bin(i).count('1')  # Count the number of '1's in the binary representation
        return arr

Java

class Solution {
    public int[] countBits(int n) {
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.bitCount(i); // Efficient way to count set bits in an integer
        }
        return arr;
    }
}

JavaScript

var countBits = function (n) {
    let arr = new Array(n + 1).fill(0);
    for (i = 1; i <= n; i++) {
        arr[i] = i.toString(2).split('0').join('').length;
    }
    return arr;
};