Monday, June 6, 2016

Leetcode: 338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
Example:
For num = 5 you should return [0,1,1,2,1,2].
Follow up:
  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
  • Space complexity should be O(n).
  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
Hint:
  1. You should make use of what you have produced already.
  2. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
  3. Or does the odd/even status of the number help you in calculating the number of 1s?
Solution considering odd/even status of the number:
In this solution, we can think about if the number if even or odd. If the number is even, the number of 1s equal to the number which is half of it. For e.g., the number 8 has the same 1s as the number 4. The number 10 has the same amount of 1 bits as number 5. That is because number i is just left shift by 1 bit from number i / 2. Therefore, they should have the same number of 1 bits. 

For the number as odd, e.g. 1, 3, 5, 7. The number of 1 bits is equal to the number (i - 1) plus 1. For e.g., for number 3, the number of 1 bits equals to the number 2 plus 1. For number 11, it equals to number 10 + 1. 

Code (Java):
public class Solution {
    public int[] countBits(int num) {
        if (num < 0) {
            return new int[0];
        }
        
        int[] result = new int[num + 1];
        
        for (int i = 1; i <= num; i++) {
            if ((i & 1) == 0) {
                result[i] = result[i / 2];
            } else {
                result[i] = result[i - 1] + 1;
            }
        }
        
        return result;
    }
}

Update on 6/1/18:
class Solution {
    public int[] countBits(int num) {
        int[] dp = new int[num + 1];
        
        for (int i = 1; i < dp.length; i++) {
            dp[i] = dp[i & (i - 1)] + 1;
        }
        
        return dp;
    }
}

3 comments:

  1. public int[] countBits(int num) {

    int a[] = new int[num+1];
    for(int i=1; i<=num; i++){
    a[i] = (i%2) + a[i/2];
    }
    return a;
    }

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. This question can be solved using DP with bitmasking.
    The basic intuition behind bottom-up approach is that we are going to directly access number of set bits in the number having value current_number/2 and we are also going to check whether last bit is set in this current_number or not by just doing and operation with 1.

    current_number/2 or current_number>>1 basically removes the last bit of this current_number so to include that bit in our count we have to manually check the last bit of this number using & operation.

    This would be expression for computing number of set bits in a number i
    dp[i]=dp[i>>1]+(i&1)


    If you still get stuck while solving this question then you can refer to the following video for better explanation
    Video Link:-
    https://youtu.be/fCvfud4p6No

    ReplyDelete