Shortest Binarian
給一個 array,binarian 是指裡面的所有元素做 2 的次方後相加,
現在求一個最小 array 可以表示這個 binarian
EX: A=[1, 0, 2, 0, 0, 2] => binarian(A) = 13, shortest binarian = [0, 2, 3]
這題一看到可以想到將所有數字加起來,再一直去做 2 的對數就知道需要哪些數字,
可是當元素的值很大時,這樣就沒用了,
換個方式想,一個元素值的 2 次方,不就表示在那個位置的 binary 要寫 1 嗎?
例如: 2^5 => 100000, 2^10000 => 第一萬位要寫 1
又當兩個同樣的冪次相加才會再進一個冪次, 2^3 + 2^3 = 2^4
所以我們只要紀錄一個 [冪次:個數] 的 map 在從低位一直進到高位就知道到底需要幾個 2 了