LeetCode 338: Counting Bits

Problem Overview

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of set bits in the binary representation of i.

• Example: n = 5 → Output: [0, 1, 1, 2, 1, 2]

• Constraints: 0 <= n <= 10^5

Solution 1: Brute Force

This is the most intuitive approach. We iterate through each number from 0 to n, and for each number, we manually count its set bits.

The Algorithm for counting bits of a single number i:

1. Initialize a counter for the current number, e.g., count = 0.

2. Use a temporary variable temp_num = i to avoid modifying the main loop’s counter.

3. Use a while loop that continues as long as temp_num is not 0.

4. Check the LSB: Use the bitwise AND operator(&) to check if the least significant bit is a 1.

5. Shift to the Next Bit: Use the right shift operator (>>) to discard the LSB.

6. The loop terminates when the number becomes 0.

C++ implementation:

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1);
        for (int i = 0; i <= n; ++i) {
            // Logic to count bits for each number 'i'
            int count = 0;
            int temp_num = i;
            while (temp_num != 0) {
                if ((temp_num & 1) == 1) { // or simply: if (temp_num & 1)
                    count++;
                }
                temp_num = temp_num >> 1;
            }
            ans[i] = count;
        }
        return ans;
    }
};

Complexity Analysis:

• Time Complexity: O(n * log(n))

  • The outer for loop runs n + 1 times.

  • The inner while loop runs for a number of times equal to the number of bits in i, which is approximately log(i).

• Space Complexity: O(n)

  • We need O(n) space for the ans array that we return.