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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.