Question

Formatted question description: https://leetcode.ca/all/338.html

 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 1:

 Input: 2
 Output: [0,1,1]


 Example 2:

 Input: 5
 Output: [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.

 @tag-dp

Algorithm

DP: countAtNum[i] = countAtNum[i>>1] + (i&1);

Code

Java

  • 
    public class Counting_Bits {
        class Solution {
            public int[] countBits(int num) {
                int[] countAtNum = new int[num + 1];
    
                if (num <= 0) {
                    return countAtNum;
                }
    
                countAtNum[0] = 0; // to be explicit
                countAtNum[1] = 1;
    
                for (int i = 2; i <= num; i++) {
                    // @note @memorize : & operator lower than +, so should be in ()
                    countAtNum[i] = countAtNum[i>>1] + (i&1);
                }
    
                return countAtNum;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/counting-bits
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        vector<int> countBits(int n) {
            vector<int> ans(n + 1);
            for (int i = 1; i <= n; i *= 2) {
                ans[i] = 1;
                for (int j = 1; j < i && i + j <= n; ++j) ans[i + j] = ans[i] + ans[j];
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        if num == 0:
          return [0]
        ans = [0, 1]
        j = 0
        for i in range(2, num + 1):
          ans.append(ans[i & (i - 1)] + 1)
        return ans
    
    

All Problems

All Solutions