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

338 - Counting Bits

Question

Algorithm

Code

All Problems

All Solutions