Set bits 0 to n
Given a non-negative integer n (0 <= n <= 10^9), return the total number of set bits (1s) across the binary representations of every integer from 0 to n inclusive. For example for n = 5 the values 0..5 in binary contribute 0+1+1+2+1+2 = 7 set bits. An O(n) loop popcounting each number is too slow at the upper bound.
Implement
count_set_bits_upto(n: int) → intExamples
in
[5]out7What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 30 min
solution.py
InputExpectedGot
[5]7not run yetsample