Home | Projects | Notes > Problem Solving > LC - E - 338. Counting Bits

LC - E - 338. Counting Bits

Solutions in C++

Solution 1

Complexity Analysis:

$T = O(n\log n)$ $n$ is the given integer
$S = O(1)$ as no additional memory is needed

Solution:


xxxxxxxxxx
24
1
class Solution {
2
public:
3
    vector<int> countBits(int n) {
4
        vector<int> ans;
5

6
        /* outerloop T = O(n), inner loop T = O(log n) */
7
        for (int i = 0; i <= n; i++)
8
        {
9
            int sum = 0;
10
            int num = i;
11
            
12
            while (num > 0 )
13
            {
14
                sum += num % 2;
15
                num /= 2;
16
            }
17

18
            ans.push_back(sum);
19
            sum = 0;
20
        }
21

22
        return ans;
23
    }
24
};

Solution 2

$i^{th}$ $(i/2)^{th}$ element, and the relationship between odd and even elements. It has better time complexity than that of Solution 1's.

Complexity Analysis:

$T = O(n)$ $n$ is the given integer
$S = O(1)$ as no additional memory is needed

Solution:


xxxxxxxxxx
13
1
class Solution {
2
public:
3
    vector<int> countBits(int n) {
4
        vector<int> ans(n + 1);
5

6
        ans.at(0) = 0;  /* this operation will result it out-of-range error on a vector of size 0 */
7

8
        for (int i = 1; i <= n; i++)
9
            ans.at(i) = ans.at(i / 2) + i % 2;
10

11
        return ans;
12
    }
13
};


xxxxxxxxxx
13
1
class Solution {
2
public:
3
    vector<int> countBits(int n) {
4
        vector<int> ans(n + 1);
5

6
        ans[0] = 0; /* this operation will result in undefined behavior on a vector of size 0 */
7

8
        for (int i = 1; i <= n; i++)
9
            ans[i] = ans[i / 2] + i % 2;
10

11
        return ans;
12
    }
13
};

Calling operator [], front(), and back() for an empty container always results in undefined behavior. Only at() operator checks for range validity.