Welcome to Subscribe On Youtube

Question

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

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

 

Follow up:

  • It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
  • Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Algorithm

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

Code

  • 
    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;
            }
        }
    }
    
    ############
    
    class Solution {
        public int[] countBits(int n) {
            int[] ans = new int[n + 1];
            for (int i = 1; i <= n; ++i) {
                ans[i] = ans[i & (i - 1)] + 1;
            }
            return ans;
        }
    }
    
  • // 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:
        def countBits(self, n: int) -> List[int]:
            ans = [0] * (n + 1)
            for i in range(1, n + 1):
                ans[i] = ans[i & (i - 1)] + 1
            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
    
    
  • func countBits(n int) []int {
    	ans := make([]int, n+1)
    	for i := 1; i <= n; i++ {
    		ans[i] = ans[i&(i-1)] + 1
    	}
    	return ans
    }
    

All Problems

All Solutions