Welcome to Subscribe On Youtube
338. Counting Bits
Description
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_popcountin C++)?
Solutions
-
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; } } -
class Solution { public: vector<int> countBits(int n) { vector<int> ans(n + 1); for (int i = 0; i <= n; ++i) { ans[i] = __builtin_popcount(i); } 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 -
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 } -
function countBits(n: number): number[] { const ans: number[] = Array(n + 1).fill(0); for (let i = 1; i <= n; ++i) { ans[i] = ans[i & (i - 1)] + 1; } return ans; }