Show problems as
Classic problem #338EasyDynamic ProgrammingBit Manipulation

Counting Bits

Real-world version: Lit Lamps Per Ticket Id
Tracked in this browser only
Read Counting Bits on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A queue display shows a ticket id in binary on a row of lamps: a lamp is lit for each 1 in the binary form of the id, and dark for each 0. Ids run from 0 up to n inclusive.

Report the lit lamp count for each id in turn, starting at id 0 and finishing at id n, so the reported list holds one more entry than n. Id 0 lights nothing.

Aim for a running time linear in n, without a fresh scan of the bits of every id.

Examples

Example 1

Input
n = 9
Output
[0, 1, 1, 2, 1, 2, 2, 3, 1, 2]

Ids 0 to 9 in binary are 0, 1, 10, 11, 100, 101, 110, 111, 1000 and 1001, so the lit lamp counts run 0, 1, 1, 2, 1, 2, 2, 3, 1, 2.

Example 2

Input
n = 13
Output
[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3]

The counts for ids 0 to 9 are unchanged, and ids 10 to 13 are 1010, 1011, 1100 and 1101, lighting 2, 3, 2 and 3 lamps.

Example 3

Input
n = 0
Output
[0]

Only id 0 exists and it lights no lamp, so the answer holds a single zero.

Constraints

  • 0 <= n <= 10^5
  • The returned array has n + 1 entries, and every entry is at most 17.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_bits(n: int) -> list[int]:
Java
public int[] countBits(int n)

More on the same topics