Counting Bits

EASY✓ CHIP-TIMEDLC #338 — FULL STATEMENT ↗

The drill: For every integer from 0 up to n, report how many of its bits are 1 — one array of answers, and the trick is reusing work you already did.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A single non-negative integer n arrives, and the task is to hand back an array covering every integer from 0 through n in order, one entry per value.

Each entry at index i must equal the count of 1-bits in the binary form of i — position 0 always reports zero, since zero has no set bits of its own.

The array's length is fixed at n + 1, and the order always matches the value being described, so index i is the popcount of i itself, never of some other number.

EX 01

n = 0

→ [0]

MINIMUM SIZE, JUST ZERO

EX 02

n = 1

→ [0, 1]

ZERO AND ONE

EX 03

n = 2

→ [0, 1, 1]

TWO IS A SINGLE BIT AGAIN

n is a single non-negative integer, and can be zero
the output array always has exactly n + 1 entries, ordered by index
every entry is a non-negative bit count, never negative
n can run from tiny up to a value in the hundreds of thousands

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Popcount-ing each number from scratch works but repeats effort — the answer for i is hiding inside the answer for a smaller number you already computed.

HINT 2 THE STRUCTURE

Drop the lowest bit of i by shifting right one place, and you land on a number you've already scored. What did that shift throw away?

HINT 3 ONE STEP FROM THE ANSWER

dp[i] = dp[i >> 1] + (i & 1) — the popcount of i's smaller half plus whichever bit the shift discarded. Build the table left to right.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE TABLE OF ONESPATTERN · BUILD ON i >> 1n = 5

STEP 1

dp[0] is always 0 — zero has no set bits. Every later index reuses an answer already sitting earlier in the table.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/counting-bits.py — RACE PACE

LANG ▸

PACE ▸

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

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 6 LN

class Solution:
    def countBits(self, n: int) -> List[int]:
        def popcount(x: int) -> int:
            c = 0
            while x:
                c += x & 1
                x >>= 1
            return c

        return [popcount(i) for i in range(n + 1)]

TIME O(N LOG N)SPACE O(N)PYTHON · TRAINING PACE · 10 LN

class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 9 LN

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int x = i;
            int c = 0;
            while (x != 0) {
                c += x & 1;
                x >>= 1;
            }
            result[i] = c;
        }
        return result;
    }
}

TIME O(N LOG N)SPACE O(N)JAVA · TRAINING PACE · 15 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED