Total set bits across 1..n

Question

Given n, compute the total number of 1-bits across all integers from 1 to n. Return the running total. Counting each number independently is O(n \log n), aim for O(n).

Accepted Answer

Build the popcount table with the standard DP bits[i] = bits[i 1] + (i & 1) (strip the last bit, which leaves a smaller already-solved value, then add it back), and accumulate as you go: Tracing n = 5: bits = [0, 1, 1, 2, 1, 2], and the running sum is 1 + 1 + 2 + 1 + 2 = 7. Time O(n), space O(n) for the table. There is also a closed-form O(\log n) route: for each bit position b, the count of integers in [1, n] with that bit set follows a fixed full-cycle-plus-remainder pattern, sum those contributions. Name it as the follow-up when interviewers push past linear. Takeaway. Reuse the popcount r…

Total set bits across 1..n

Your answer

More Coding questions