🎨 Try our Free AI Image Generation Feature

338. Counting Bits

avatar
Dare2Solve

10 months ago

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;
};