221. Count Total Set Bits From 1 to N

Given a non-negative integer n, find the total number of set bits across the binary representations of every integer from 1 to n (inclusive).

Input: A single line contains the integer n. Output: Print a single integer - the total count of set bits across all numbers from 1 to n.

0 <= n <= 10^9

The key mathematical fact worth memorizing: in any range of 2^k consecutive numbers starting from a multiple of 2^k, exactly half have any specific bit position turned on - this single observation is what makes the fast solution possible.

For every single number from 1 up to N, write it in binary and count how many 1s it has. Now add up ALL of those counts across every number. That grand total is the answer. Brute force: Loop through every number from 1 to N, and for each one, count its set bits individually (checking each bit or using n & (n-1) repeatedly) - correct, but for N up to a billion, this means a billion separate bit-counting operations, which is too slow. Optimised: Rather than counting bit-by-bit for every number, use the mathematical pattern that within any complete power-of-two-sized block of numbers, exactly half have a given bit set - this lets you compute the total in a number of steps proportional to the number of BITS in N (about 30), not the value of N itself.

For every integer from 1 to n, count its set bits individually, either by checking each bit position or by repeatedly clearing the lowest set bit with Brian Kernighan's trick (num &= num - 1) until it becomes 0, adding that count to a running total. This correctly totals every set bit but redoes bit-counting work from scratch for each number instead of reusing anything already learned from smaller numbers. Time: O(n log n) Space: O(1)

Build a table where countBits[i] = countBits[i >> 1] + (i & 1): the number of set bits in i equals the set-bit count of i with its last bit dropped, plus 1 if that dropped bit was a 1. Filling this table for every i from 1 to n and summing it reuses previously computed results instead of recomputing from scratch, dropping the per-number cost from O(log n) to O(1) amortized. Time: O(n) Space: O(n)

For each bit position separately (there are only about log2(n) of them), count directly how many numbers from 1 to n have that bit set, using the fact that within every complete block of 2^(i+1) consecutive numbers exactly 2^i of them have bit i set, plus any leftover partial block contributing max(0, remainder - 2^i) more. Summing this formula over all bit positions gives the total set-bit count without ever touching the numbers individually. Time: O(log n) Space: O(1)

1. Notice that among all numbers from 0 to 2^k - 1 (a full block of k-bit numbers), exactly half of them have any given bit position set. 2. Build up the total set-bit count block by block, doubling the block size each time, rather than checking every single number individually. 3. For the remaining numbers beyond the last full block (up to N itself), add their set-bit counts using the same recursive idea on the smaller leftover range. 4. Sum everything together for the final total.

Time: Proportional to the number of bits in N (around 30 steps for values up to a billion) - essentially instant, regardless of how large N actually is. Space: O(1) - just a few running totals, no matter how large N is.

Test n = 0 (no numbers to count, answer 0) and the upper bound n = 10^9, which rules out a naive per-number bit-counting loop and requires the bit-length pattern approach.

This is a good example of trading a 'loop over every value' brute force for a 'reason about the mathematical pattern' approach - interviewers often use it to check if you look for structure instead of just iterating blindly.