💬 Discord
Sign In
NeetCode #854LC-338EasyBit ManipulationBlind 75NC 150NC 250
← Back to All Problems

#854 · #338 · Counting Bits(比特位计数)

📌 Problem Statement & Constraints

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of set bits in the binary representation of i, for every 0 <= i <= n. Constraints: 0 <= n <= 10^5. The follow-up asks for a linear-time solution that does not call a popcount routine for every index.

💡 Core Algorithmic Approaches

  1. Use dynamic programming over the numbers themselves: the bit count of i can be built from a smaller number in O(1).
  2. Recurrence one: ans[i] = ans[i >> 1] + (i & 1) -- the count of the number with its lowest bit dropped, plus that bit.
  3. Recurrence two: ans[i] = ans[i & (i - 1)] + 1 -- strip the lowest set bit and add one.
  4. Both make the whole table O(n) because each entry reuses an already-computed smaller index.

💻 Benchmark Python3 Implementation

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)   # drop the lowest bit, add it back
        return ans


# Alternative recurrence: strip the lowest set bit
class Solution2:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i & (i - 1)] + 1
        return ans

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one constant-time step per index.
💾 Space Complexity
O(n): the output array itself.

⚠️ Interview Pitfalls & Follow-ups

  • Calling a per-number popcount: that is O(n log n) or O(32n); the DP reuses earlier results for O(n).
  • Off-by-one in the array size: the answer has n + 1 entries because the range includes both 0 and n.
  • Writing ans[i // 2] + i % 2 and forgetting the base: ans[0] must be 0, which the initialisation already provides.
  • Starting the loop at 0: ans[0] is the base case; starting at 1 avoids re-deriving it.