
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
has0
bits set to1
.1
has1
bit set to1
.2
has1
bit set to1
.3
has2
bits set to1
.4
has1
bit set to1
.5
has2
bits set to1
.
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
- Initialization: Create an array
arr
of sizen+1
filled with zeros. - Iteration: Loop through each integer
i
from1
ton
: - Converti
to its binary form and count the number of1
bits. - Store the result inarr[i]
. - Return: After the loop completes, the array
arr
will contain the number of1
bits for each integer from0
ton
.
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;
};