Skip to content

Volume ITechnology

4.30.3 — Counting Bits ​

LeetCode 338 · Easy · ★ Blind 75

The problem ​

Return an array where entry i is the number of set bits in i, for every i from 0 to n.

n = 5   →  [0,1,1,2,1,2]
    0 = 000 → 0
    1 = 001 → 1
    2 = 010 → 1
    3 = 011 → 2
    4 = 100 → 1
    5 = 101 → 2

The follow-up asks for one pass without calling a built-in popcount.

The pattern ​

Calling 4.30.2 for every number is O(n \log n). The linear solution comes from noticing that the answer for i is already in the array.

i >> 1 is i with its last bit dropped. So i has the same bits as i >> 1, plus possibly one more — the bit that was dropped.

\text{bits}[i] = \text{bits}[i \gg 1] + (i \,\&\, 1)

i >> 1 is always smaller than i, so its answer is already computed. That is a DP recurrence with an obvious fill order, and it is one line.

Check it: 5 = 101. 5 >> 1 = 2 = 010, which has 1 bit. 5 & 1 = 1. So 1 + 1 = 2 ✓.

The solution ​

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

        for i in range(1, n + 1):  # (2)
            bits[i] = bits[i >> 1] + (i & 1)      # (3) drop the last bit, add it back

        return bits  # (4)
ts
function countBits(n: number): number[] {
  const bits = new Array(n + 1).fill(0);  // (1)

  for (let i = 1; i <= n; i++) {  // (2)
    bits[i] = bits[i >> 1] + (i & 1);  // (3)
  }

  return bits;  // (4)
}

Line by line ​

(1) bits[i] will hold the number of 1 bits in i. bits[0] is 0.

(2) Work out each number from 1 to n, smallest first.

(3) Reuse the answer for i with its last bit removed. i >> 1 shifts every bit one place right, which drops the last bit. That is i \div 2 rounded down, which is smaller than i, so its answer is already known. Then add the dropped bit back: i & 1 is 1 if the last bit was 1, and 0 otherwise.

(4) The list of counts.

Trace ​

iBinaryi >> 1bits[i >> 1]i & 1bits[i]
110011
2101101
3111112
41002101
51012112

i >> 1 is integer division by 2, and it is exactly "remove the last binary digit".

i & 1 is the last bit — 1 if odd, 0 if even.

bits[0] = 0 comes free from the initialisation, and the loop starts at 1 so nothing reads a negative index.

The other recurrence ​

There is a second one-liner, using the idiom from 4.30.2:

\text{bits}[i] = \text{bits}[i \,\&\, (i-1)] + 1

i & (i-1) is i with its lowest set bit cleared — so it has exactly one fewer set bit, and it is smaller, so its answer is ready.

Both are O(n) and both are one line. The i >> 1 version is easier to explain, because "drop the last digit" is a sentence anyone follows.

A third exists, based on powers of two: for i between 2^k and 2^{k+1}, bits[i] = bits[i - 2^k] + 1. It needs an extra variable tracking the current power, so it is the least clean of the three.

Knowing that all three exist and picking the clearest is the answer to this problem.

Edge cases ​

  • n = 0. The answer is [0].
  • Powers of two, like 8. They have exactly one 1 bit, and the formula gives bits[4] + 0 = 1.

Complexity ​

O(n) time, O(n) space for the output — which is required, since the output has n + 1 entries.

Against the naive O(n \log n): for n = 100,000 that is 100,000 operations instead of about 1.7 million.

Why this is really a DP problem ​

It is filed under bit manipulation, but the method is 4.23's:

  • State: bits[i] = the number of set bits in i.
  • Recurrence: built from a strictly smaller subproblem.
  • Base case: bits[0] = 0.
  • Fill order: ascending, because i >> 1 < i.

The bit trick is only how you find the subproblem. Recognising that a bitwise operation produces a smaller instance of the same question is the transferable move, and it is exactly what bitmask DP does at a larger scale (4.29).

Where this goes next ​

  • Number of 1 Bits — the single-number version. 4.30.2.
  • Bitmask DP — where the population count of a mask is part of the state, and precomputing it for every mask uses exactly this loop.
  • Gray code — consecutive values differing by one bit, built with a related recurrence.

What the interviewer will push on ​

"Derive the recurrence." i >> 1 drops the last bit, so add it back with i & 1. Check it on 5.

"Why is the fill order safe?" i >> 1 is strictly smaller.

"Is there another recurrence?" bits[i & (i-1)] + 1. Say why you preferred the other.

"Why is this O(n) and not O(n \log n)?" Each entry is one lookup and one addition, not a full bit scan.

"Is this bit manipulation or DP?" Both — DP with a bitwise operation finding the subproblem. Saying that shows you see the structure.

One thing to volunteer: name it as DP explicitly. The problem sits in the bit chapter, and pointing out that the method comes from elsewhere is the kind of cross-connection that makes patterns transfer.

Next: 4.30.4 Reverse Bits — a loop that reads from one end and writes to the other.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet