LeetCode 338 - Counting Bits

The problem asks us to compute the number of set bits, also called population count or popcount, for every integer from 0 through n. A set bit is a bit with value 1 in the binary representation of a number.

leetcodeeasydynamic-programmingbit-manipulation

LeetCode Problem 338

Difficulty: 🟢 Easy
Topics: Dynamic Programming, Bit Manipulation

Solution

Problem Understanding

The problem asks us to compute the number of set bits, also called population count or popcount, for every integer from 0 through n.

A set bit is a bit with value 1 in the binary representation of a number. For example:

  • 5 in binary is 101, which contains two 1 bits
  • 7 in binary is 111, which contains three 1 bits
  • 0 in binary is 0, which contains zero 1 bits

The input is a single integer n. The expected output is an array ans where:

  • ans[i] equals the number of 1 bits in the binary representation of i
  • the array contains results for every integer from 0 to n
  • therefore, the output length is always n + 1

For example, if n = 5:

Number Binary Count of 1s
0 0 0
1 1 1
2 10 1
3 11 2
4 100 1
5 101 2

So the output becomes:

[0,1,1,2,1,2]

The constraint 0 <= n <= 10^5 is important because it tells us that the solution must be efficient. A naive solution that repeatedly converts numbers to binary strings or counts bits individually can work, but the follow-up specifically asks for an O(n) solution without built-in popcount functions.

This strongly suggests that we should reuse previously computed results instead of recomputing bit counts from scratch for every number.

Several edge cases are important:

  • n = 0, the smallest possible input
  • powers of two such as 1, 2, 4, 8, because they contain exactly one set bit
  • numbers immediately after powers of two, such as 3, 5, 9, where the binary structure changes
  • the maximum value 10^5, which tests performance and memory efficiency

The problem guarantees that n is non-negative, so we never need to handle invalid or negative inputs.

Approaches

Brute Force Approach

The brute-force solution computes the number of set bits independently for every integer from 0 to n.

For each number:

  1. Examine its binary representation
  2. Count how many bits are equal to 1
  3. Store the result in the output array

One way to do this is repeatedly dividing the number by 2 or using bitwise operations like:

count += num & 1
num >>= 1

This works because each iteration processes one binary digit.

The approach is correct because every bit in every number is examined exactly once, so the count is accurate.

However, this solution is too slow for the follow-up requirement. Each number may require up to O(log n) bit operations, and we do this for all numbers from 0 to n.

That produces a total complexity of:

O(n log n)

We can do better by observing relationships between consecutive numbers.

Key Insight for the Optimal Solution

The important observation is that many numbers are closely related in binary form.

Consider these examples:

Number Binary Set Bits
0 000 0
1 001 1
2 010 1
3 011 2
4 100 1
5 101 2

Notice this pattern:

5 = 4 + 1
101 = 100 + 1 bit

Similarly:

6 = 3 * 2
110 has same set bits as 11

A very useful recurrence emerges:

bits[i] = bits[i >> 1] + (i & 1)

Explanation:

  • i >> 1 removes the last binary bit

  • (i & 1) tells us whether the last bit was 1

  • therefore, the total set bits equal:

  • the set bits in the shifted number

  • plus one if the removed bit was 1

This allows dynamic programming because each result depends on a smaller already-computed result.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(1) excluding output Counts bits independently for every number
Optimal O(n) O(n) Uses dynamic programming and bit relationships

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

  1. Create an array result of size n + 1.

We need one answer for every number from 0 through n. Initializing the array upfront gives us direct indexed access. 2. Set result[0] = 0.

The number 0 contains no set bits, so this is our base case. 3. Iterate through all integers from 1 to n.

For every number, we compute its answer using a previously solved smaller subproblem. 4. For each number i, compute:

result[i] = result[i >> 1] + (i & 1)

Here:

  • i >> 1 removes the least significant bit

  • result[i >> 1] gives the number of set bits in the remaining prefix

  • (i & 1) equals:

  • 1 if the last bit is set

  • 0 otherwise

Adding them together gives the total number of set bits. 5. Continue until all values are filled.

Since every i >> 1 is smaller than i, the required subproblem has already been computed. 6. Return the completed array.

Why it works

The algorithm relies on the binary decomposition property:

i = (i >> 1) * 2 + (i & 1)

Shifting right removes the final bit. The number of set bits in i must therefore equal:

  • the set bits in the shifted value
  • plus one if the removed bit was 1

Because we process numbers in increasing order, every smaller subproblem is already solved when needed. This guarantees correctness for all values from 0 to n.

Python Solution

from typing import List

class Solution:
    def countBits(self, n: int) -> List[int]:
        result = [0] * (n + 1)

        for i in range(1, n + 1):
            result[i] = result[i >> 1] + (i & 1)

        return result

The implementation begins by allocating an array of size n + 1. Every index in this array corresponds directly to a number whose bit count we want to compute.

The loop starts from 1 because result[0] is already correct by initialization.

Inside the loop:

i >> 1

removes the least significant bit, and:

i & 1

checks whether that removed bit was 1.

The recurrence combines these two pieces of information to compute the answer in constant time per number.

Because each result depends only on a smaller already-computed value, the dynamic programming table fills efficiently in a single pass.

Go Solution

func countBits(n int) []int {
    result := make([]int, n+1)

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

    return result
}

The Go implementation follows the same logic as the Python solution.

A slice of length n + 1 is created using make. All elements are initialized to 0 automatically, so the base case for 0 already exists.

The bitwise operations behave identically:

  • i >> 1 performs right shift
  • i & 1 extracts the least significant bit

Unlike Python, Go uses fixed integer types, but integer overflow is not a concern here because the maximum number of set bits for 10^5 is very small.

The function returns a slice rather than an array because slices are the idiomatic dynamic sequence structure in Go.

Worked Examples

Example 1

Input:

n = 2

We create:

result = [0, 0, 0]

Now iterate from 1 to 2.

i Binary i >> 1 result[i >> 1] i & 1 result[i]
1 1 0 0 1 1
2 10 1 1 0 1

Final array:

[0,1,1]

Example 2

Input:

n = 5

Initial state:

result = [0,0,0,0,0,0]

Now process each number.

i Binary i >> 1 result[i >> 1] i & 1 result[i]
1 1 0 0 1 1
2 10 1 1 0 1
3 11 1 1 1 2
4 100 2 1 0 1
5 101 2 1 1 2

Final result:

[0,1,1,2,1,2]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each number from 1 to n is processed once
Space O(n) The output array stores n + 1 results

The algorithm performs constant work for each integer. Every iteration uses only a few bitwise operations and array lookups, all of which are O(1).

The space complexity is O(n) because we store one computed value for every number from 0 to n. The output array itself dominates memory usage.

Test Cases

from typing import List

class Solution:
    def countBits(self, n: int) -> List[int]:
        result = [0] * (n + 1)

        for i in range(1, n + 1):
            result[i] = result[i >> 1] + (i & 1)

        return result

solution = Solution()

assert solution.countBits(0) == [0]                  # minimum input
assert solution.countBits(1) == [0, 1]              # smallest non-zero case
assert solution.countBits(2) == [0, 1, 1]           # example case
assert solution.countBits(5) == [0, 1, 1, 2, 1, 2] # example case
assert solution.countBits(8) == [0,1,1,2,1,2,2,3,1] # power of two
assert solution.countBits(10) == [0,1,1,2,1,2,2,3,1,2,2] # mixed values
assert solution.countBits(15) == [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4] # all 4-bit numbers
assert solution.countBits(16)[16] == 1              # another power of two
assert solution.countBits(31)[31] == 5              # all lower five bits set
assert len(solution.countBits(100000)) == 100001    # maximum constraint size

Test Summary

Test Why
n = 0 Validates minimum boundary input
n = 1 Confirms smallest positive number handling
n = 2 Verifies provided example
n = 5 Verifies provided example with mixed bit patterns
n = 8 Tests power of two behavior
n = 10 Tests mixed even and odd numbers
n = 15 Validates consecutive binary growth
n = 16 Ensures powers of two produce exactly one set bit
n = 31 Tests numbers with many set bits
n = 100000 Confirms scalability and constraint handling

Edge Cases

One important edge case is n = 0. A naive implementation might accidentally return an empty list because there are no positive integers to process. However, the problem explicitly requires results for all numbers from 0 to n, inclusive. Therefore, the correct answer must be [0]. The implementation handles this naturally because the array is initialized with one element and the loop does not execute.

Another important edge case involves powers of two such as 1, 2, 4, 8, and 16. These numbers contain exactly one set bit in binary form. Some incorrect implementations accidentally overcount due to faulty recurrence relations or indexing mistakes. In this solution, powers of two work correctly because:

1000 >> 1 = 100

and the least significant bit becomes 0, preserving the correct count relationship.

A third important edge case is numbers with all bits set, such as 3, 7, 15, and 31. These values maximize the number of 1 bits for their bit length. They are useful for detecting incorrect transitions in dynamic programming formulas. The recurrence:

result[i] = result[i >> 1] + (i & 1)

correctly accumulates the additional set bit at each step, producing the expected counts.

The maximum constraint n = 100000 is also significant. A slower O(n log n) implementation may still pass, but the follow-up explicitly asks for linear time. This dynamic programming solution scales efficiently because each number is processed exactly once with constant-time work.