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 timeO(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 }