Monday, April 22, 2024 8:15 EDT

Leetcode 338. Counting Bits (Easy)

Approach
I struggled with this initially. It has been a while since I did anything with bit manipulation and I forgot about some of the tricks you can use when trying to work with bits. For example, right shifting to remove the least significant bit (LSB) and also modulo 2 for getting the LSB.

My idea is to start a loop that runs n + 1 times -- a pattern I noticed immediately since the output is an array that is 1 more than the input number. I also set the vector to this size as well.

Then for each index, starting at 0, we assign this index to a temp variable so as to not interfere with the outer loop. This temp variable represents the index we are working with. We can now manipulate it using bitshift operations to understand the number of 1's in it's bit representation.

To do this, I used a while-loop to iterate over temp until it equals 0. Inside the while-loop we get the LSB and then remove it. In other words, if i = 5 the inner loop looks like this:

temp == 5; // 0101
res[5] += 1;
temp == 2; // 0010
res[5] += 0;
temp == 1; // 0001
res[5] += 1;
temp == 0;

Complexity
Time Complexity: O(n log n)
Space Complexity: O(n)

Code

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res = vector<int>(n+1);
        for(int i = 0; i <= n; i++){
            int temp = i;
            while(temp != 0){
                res[i] += temp % 2;
                temp >>= 1;
            }
        }
        return res;
    }
};