Solution: Counting Bits

Statement

Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach for this solution would be to iterate through the string character by character. During the traversal, we convert each number to its binary representation, count the number of $1$ bits in each binary representation, and store the result in an array.

This approach would have a time complexity of $O(n \log n)$ ...