Algorithm
Problem Name: 338. Counting Bits
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
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
Constraints:
0 <= n <= 105
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int* countBits(int num, int* returnSize) {
int *p, i;
p = malloc((num + 1) * sizeof(int));
//assert(p);
*returnSize = num + 1;
p[0] = 0;
for (i = 1; i < = num; i ++) {
p[i] = p[i & (i - 1)] + 1; // i & (i - 1) is to remove a bit from tail
}
return p;
}
Input
n = 2
Output
[0,1,1]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] countBits(int n) {
int[] numofOnes = new int[n + 1];
for (int i = 1; i < = n; i++) {
numofOnes[i] = numofOnes[i / 2] + i % 2;
}
return numofOnes;
}
}
Input
n = 2
Output
[0,1,1]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const countBits = function (num) {
const f = new Array(num + 1).fill(0)
for (let i = 1; i < = num; i++) f[i] = f[i >> 1] + (i & 1)
return f
}
Input
n = 5
Output
[0,1,1,2,1,2]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def countBits(self, num: int) -> List[int]:
return [bin(i)[2:].count('1') for i in range(num + 1)]
Input
n = 5
Output
[0,1,1,2,1,2]
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0338_CountingBits
{
public int[] CountBits(int num)
{
var result = new int[num + 1];
int b = 1;
while (b < = num)
{
var i = 0;
while (i < b && b + i <= num)
{
result[i + b] = result[i] + 1;
i++;
}
b <<= 1;
}
return result;
}
}
}
Input
n = 2
Output
[0,1,1]