Counting Bits Problem


Description

LeetCode Problem 338.

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:

1
2
3
4
5
6
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

1
2
3
4
5
6
7
8
9
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 <= 10^5


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ans;
        
        ans.push_back(0);
        if (num == 0)
            return ans;
        
        int b = 0, e = 1;
        
        for (int i = 1; i <= num; i ++) {
            ans.push_back(ans[b] + 1);
            b ++;
            if (b == e) {
                b = 0;
                e = i + 1;
            }
        }
        return ans;
    }
};




Related Posts

Counting Bits Problem

LeetCode 338. Given an integer n, return an array ans...

Bitwise And Of Numbers Range Problem

LeetCode 201. Given two integers left and right that represent...

Reverse Bits Problem

LeetCode 190. Reverse bits of a given 32 bits unsigned...

Number Of 1 Bits Problem

LeetCode 191. Write a function that takes an unsigned integer...

Single Number Problem

LeetCode 136. Given a non-empty array of integers nums, every...

Single Number II Problem

LeetCode 137. Given an integer array nums whereevery element appears...