Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Solution: Counting Bits

Explore how to apply dynamic programming techniques in C++ to count the set bits for every number from 0 to n. Understand the optimization of using previously computed results for even and odd numbers, resulting in an O(n) time complexity solution.

We'll cover the following...

Statement

For a given positive integer, n, your task is to return an array of length n+1n+1 such that for each xx where 0≤x≤n0 \leq x \leq n, result[x] is the count of 11s in the binary representation of xx.

Constraints:

  • 0≤n≤1040 \leq n \leq 10^4

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 11 bits in each binary representation, and store the result in an array.

This approach would have a time complexity of O(nlog⁡n)O(n \log n) and a space complexity ...