338

338. Counting Bits (Easy)

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++)?

Companies:
Amazon, Google, Apple

Related Topics:
Dynamic Programming, Bit Manipulation

Similar Questions:

• Number of 1 Bits (Easy)

Solution 1. DP

All the numbers of power of 2 only have a single bit.

For each number between 2^k and 2^(k+1), we can get them by adding 1, 2, 3, ..., 2^k - 1 to 2^k.

And 1, 2, 3, ..., 2^k - 1 doesn't have bit overlap with 2^k.

// OJ: https://leetcode.com/problems/counting-bits
// Author: github.com/lzl124631x
// 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;
    }
};

Solution 2. DP

i & -i is the lowest bit of i. Let dp[i] be the number of bits of i.

dp[i] = 1 + dp[i - (i & -i)]

// OJ: https://leetcode.com/problems/counting-bits/
// Author: github.com/lzl124631x
// 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) ans[i] = 1 + ans[i - (i & -i)];
        return ans;
    }
};

Solution 3. DP

// OJ: https://leetcode.com/problems/counting-bits
// Author: github.com/lzl124631x
// 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) ans[i] = ans[i / 2] + (i % 2);
        return ans;
    }
};

Solution 4. DP

DP based on highest bit

// OJ: https://leetcode.com/problems/counting-bits/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1);
        for (int i = 1, hb = 1; i <= n; ++i) {
            if ((hb & i) == 0) hb <<= 1;
            ans[i] = 1 + ans[i - hb];
        }
        return ans;
    }
};