Dare2Solve
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
.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.
arr
of size n+1
filled with zeros.i
from 1
to n
:
i
to its binary form and count the number of 1
bits.arr[i]
.arr
will contain the number of 1
bits for each integer from 0
to n
.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.
O(n)
for storing the result in the array.
class Solution {
public:
std::vector<int> countBits(int n) {
std::vector<int> 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;
}
};
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
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;
}
}
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;
};