Skip to main content
DSA patterns

Counting Bits

easyBits Must-doAmazonCiscoMicrosoft

Problem statement

You're given a non-negative integer n. Build an array ans of length n + 1 where ans[i] is the number of set bits (1s) in the binary representation of i, for every i from 0 up to n.

You need to compute each count yourself — you can't reach for a built-in popcount function to do it for you.

Examples

Example 1

Input: n = 2

Output: [0, 1, 1]

Explanation: 0 is 0 (no set bits), 1 is 1 (one set bit), and 2 is 10 (one set bit).

Example 2

Input: n = 5

Output: [0, 1, 1, 2, 1, 2]

Explanation: 3 is 11 and 5 is 101, both with two set bits; every other value from 0 to 5 has exactly one (or zero, for 0 itself).

Hints

Hint 1: Every number's set-bit count depends on a smaller number you've already worked out — the trick is spotting which smaller number to reuse.

Approach

Optimal: DP: drop the lowest bit

Intuition

Shifting i right by one bit (i >> 1) drops its lowest bit and is the same as i divided by 2, rounding down — a number smaller than i whose count is already known. The bit that got dropped is exactly i & 1 (1 if i is odd, 0 if even). So ans[i] = ans[i >> 1] + (i & 1): the count for i is the count for "i without its last bit" plus whatever that last bit was worth. This is the most direct possible relationship between an index and something smaller than it, and it's exactly the "single pass, O(n) time" solution the problem's own follow-up asks for.

Steps

  1. Create ans of length n + 1, with ans[0] = 0.
  2. For each i from 1 to n: look up ans[i >> 1] (already computed, since i >> 1 is smaller than i).
  3. Add i & 1 to that value and store the result in ans[i].
  4. Return ans.

Dry run

n = 5

i i >> 1 ans[i >> 1] i & 1 ans[i]
1 0 0 1 1
2 1 1 0 1
3 1 1 1 2
4 2 1 0 1
5 2 1 1 2

Result: [0, 1, 1, 2, 1, 2], matching Example 2.

Edge cases: n = 0 skips the loop entirely and returns [0].

Complexity

Time O(n) - one pass; the same O(n) as the last-set-bit approach, but with a simpler relationship between each index and the smaller one it reuses.

Space O(n) - for the output array; O(1) extra.

class Solution:
    def countBits(self, n):
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)
        return ans


if __name__ == "__main__":
    print(Solution().countBits(2))
    print(Solution().countBits(5))
RecapThe whole problem in a few lines, for the night before
  • Spot it: "set-bit count for every number from 0 to n" (not just one number)
  • Idea: each count reuses a smaller, already-computed one — either ans[i >> 1] + (i & 1) or ans[i & (i-1)] + 1
  • Cost: O(n) time, O(n) space for either DP recurrence; O(n log n) time for counting each number's bits independently
  • Trap: recomputing every number's bits from scratch instead of reusing the count already stored for a smaller index

Interview follow-ups

  • What if you needed this for a huge range that doesn't start at 0 — say, from 10,000 to 20,000?

    The recurrences here rely on smaller indices already being filled in starting from 0, so the cleanest fix is still to build the full array from 0 up to the largest value needed, then slice out the range you actually want. Building only the requested range without the earlier values would mean losing the "already computed" smaller answers the DP depends on.

  • The values you need counts for arrive one at a time, in no particular order, rather than as a clean range from 0 to n.

    Cache every count you compute (by any method — even the brute-force per-number loop) in a dictionary keyed by value, and check the cache before recomputing. Over many queries this converges toward the same amortized savings as the array-based DP, without needing to know the maximum value in advance.

Frequently asked questions

Every bit of i except the very last one is identical to the bits of i >> 1 — shifting right just removes that last bit and doesn't touch anything else. So the set-bit count of i is the set-bit count of i >> 1, plus 1 more if the bit that got dropped happened to be a 1 (which is exactly what i & 1 checks).

For small n the difference barely shows, but the problem's own follow-up asks specifically for O(n) in a single pass, since the brute-force approach recomputes overlapping work: counting the bits of 6, 12, 24, 48… all repeat the same "how many bits in 3, 6, 12…" work over and over from scratch. The DP versions do each piece of work exactly once.

Bulk-computing a small property (like set-bit count, but it could just as easily be a hash prefix or a category flag) for every value in a range, without recomputing shared work, is the same shape as precomputing a lookup table or memoized cache used across many requests. Recognizing when a per-item brute-force loop can be replaced by reusing earlier results is a core efficiency habit for this kind of role.

Number of 1 Bits counts the bits of one number in isolation. Counting Bits asks for that same count for every number from 0 to n, so the fast solutions here reuse the population-count relationships between consecutive numbers instead of solving each one from scratch the way Number of 1 Bits does for its single input.