Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary representation of i, for every i from 0 to n.
Try to do it with a single O(n) pass using previously computed answers, rather than recomputing each one from scratch.
Example
Input: n = 5
Output: [0, 1, 1, 2, 1, 2] // 0,1,1,10,1,10 in binary