public class Solution {
public int[] CountBits(int num) {
int[] counts = new int[num+1];
for(int i = 1; i < counts.Length; i++)
{
counts[i] = counts[i/2] + (i % 2);
}
return counts;
}
}
A C# solution.

This is the best solution I've seen so far. But, I am not able to figure out what approach would lead to this solution. What was your thought process?
Edit 1: I see what's going on. Bitshifting to the left doubles the number, keeping the number of 1s the same. If its an odd number, just add one more bit to the end with (i % 2). Brilliant!
Edit 2: Just saw the top voted answer too. Exact same concept, implemented with bit manipulation.