Counting Bits In a Number – Leetcode
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
Solution
This is a standard approach where we keep dividing the number by 2 until it becomes zero and count the once in remainder e.g.
RECURSIVE SOLUTION –
class Solution {
public int[] countBits(int n) {
int bits[] = new int[n+1];
for(int i = 0; i <= n; i++)
bits[i] = getBits(i);
return bits;
}
public int getBits(int n) {
if(n == 0)
return 0;
return (n%2 == 0 ? 0 : 1) + getBits(n/2);
}
}
DYNAMIC SOLUTION – We can optimise this code by avoiding repetive calculation.
class Solution {
public int[] countBits(int n) {
int bits[] = new int[n+1];
for(int i = 0; i <= n; i++)
bits[i] = getBits(i, bits);
return bits;
}
public int getBits(int n, int[] bits) {
if(n == 0)
return 0;
if(bits[n] > 0) return bits[n];
return (n%2 == 0 ? 0 : 1) + getBits(n/2, bits);
}
}