Log in to run or submit
DP on bits: popcount(i) = popcount(i>>1) + (i&1).
popcount(i) = popcount(i>>1) + (i&1)
Fill array from 1..n using the recurrence.