1304. How Often Each Bit Position Is Set Up to n

Given n, print for each bit position b from 0 to 49 how many of the values 0, 1, ..., n have bit b set. Print all fifty counts on one line.

n=0 -> 0 0 0 ... 0 n=1 -> 1 0 0 ... 0 n=3 -> 2 2 0 ... 0 n=7 -> 4 4 4 0 ... 0

## What most people try first

Fifty passes over 0..n, or one pass accumulating fifty counters. Both are O(50 n) and O(n) respectively, and at n = 10^15 neither can run. There is nothing to prune: every value contributes.

So each count has to come from the STRUCTURE of the range, one closed form per position.

## Each position is a cycle, so each count is arithmetic

As v runs upward from 0, bit b of v is 0 for 2^b values, then 1 for 2^b values, repeating with period 2^(b+1). That follows from writing v = q * 2^(b+1) + r: bit b of v is 1 exactly when r >= 2^b.

So over the n + 1 values 0..n:

block = 2^(b+1) half = 2^b full = (n + 1) / block whole periods, integer division rem = (n + 1) % block length of the trailing partial period count = full * half + max(0, rem - half)

Each whole period supplies half ones. The partial period is a PREFIX, so it begins with half zeros; it contributes nothing if it is no longer than half, and rem - half otherwise, which is what the max expresses.

## Why fifty positions is the right number

n is at most 10^15, and 2^50 = 1125899906842624 exceeds that, so bit 50 and above are never set in range and their counts would all be 0. Printing exactly fifty makes the output a fixed shape regardless of n, which is why the contract specifies it rather than "as many as are non-zero".

Positions near the top are frequently 0, which is correct and worth expecting: at n = 7 only positions 0, 1 and 2 are non-zero.

## The relation to #1303

Adding these fifty counts together gives #1303's answer: the total number of set bits over the range. That is not a coincidence, it is the same sum computed in the same order, with #1303 collapsing it and this problem showing the terms.

Checking one against the other is a genuine test, not a tautology, because an error in a single position's formula would change the total. The oracle for this block does exactly that cross-check on every declared case.

## Width

At n = 10^15 each count is about n/2 = 5 * 10^14. That is past the 2147483647 a signed 32-bit integer holds by five orders of magnitude, so every counter needs 64 bits, whose limit is 9223372036854775807.

It is ALSO past 2^53 = 9007199254740992? No: 5 * 10^14 is below 9 * 10^15, so an individual count does fit in a double exactly. Their TOTAL, which is #1303's answer, does not. The reference here still uses BigInt in JavaScript, because n itself is 10^15 and the shifts 1 << (b+1) with b up to 49 would coerce to signed 32 bits and give nonsense.

Constraints - `0 ≤ n ≤ 1000000000000000`