Problem Description

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's* in the binary representation of* i.

Examples

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints:

• 0 <= n <= 105

Follow up:

• It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
• Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

解析

給定一個非負數字 n,

回傳一個長度為 n+1 陣列 ans

陣列 ans 每個數值 ans[i] 代表數值 i 轉換成 2元表示式中非零的 bit 個數

對於 每個數值 可以發現 只要數值 是 2某個次方項 代表該 數值所使用非零的bit 數值是 1

而對於每個 ans[i] 假設存在某一個 k 使得 $2^k$ > ans[i]

則有以下關係式 ans[i] = 1 + ans[i - $2^k$]