algoadvance

Leetcode 338. Counting Bits

Problem Statement

You are given an integer n. For every number i in the range 0 to n inclusive, you need to count the number of 1’s in their binary representation and return them as an array.

The function signature is:

vector<int> countBits(int n);

Clarifying Questions

  1. Q: What is the range of the integer n?
    • A: The constraint typically lies within 0 <= n <= 10^5.
  2. Q: Should the solution be optimized in terms of time and space complexity?
    • A: Yes, ideally an O(n) time complexity solution is expected.
  3. Q: Can we assume that the input n will always be a non-negative integer?
    • A: Yes, n is guaranteed to be non-negative.

Strategy

To solve this problem efficiently, we can utilize a dynamic programming approach. The main idea is to use previously computed values to build up the result array.

  1. Observation: For any number i, the number of 1’s in its binary representation can be derived from the number of 1’s in the binary representation of i/2 plus the least significant bit of i.
    • If i is even, the number of 1s in i is the same as in i/2.
    • If i is odd, it has one more 1 than i-1 (which is even).
  2. Formula:
    • countBits[i] = countBits[i >> 1] + (i & 1)
      • i >> 1 effectively performs integer division by 2.
      • i & 1 extracts the least significant bit (0 if i is even, 1 if i is odd).

Code

Here is the efficient C++ solution:

#include <vector>
using namespace std;

vector<int> countBits(int n) {
    vector<int> result(n+1);
    result[0] = 0; // Base case: The number of 1's in the binary representation of 0 is 0

    for (int i = 1; i <= n; ++i) {
        result[i] = result[i >> 1] + (i & 1);
    }

    return result;
}

Time Complexity

This method efficiently computes the number of 1’s in the binary representations of all numbers from 0 to n using dynamic programming.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI