Every positive integer can be uniquely represented as a sum of different positive powers of two.
Given a number n, return a sorted array of different powers of two that sum up to n.
Example
For n = 5, the output should be
powersOfTwo(n) = [1, 4].
Input/Output
[time limit] 4000ms (py)
[input] integer n
A positive integer.
Constraints:
5 ≤ n ≤ 6000.
[output] array.integer
An array of different powers of two, in ascending order.
Solution
def powersOfTwo(n):
a=[]
x=1
while n:
if n&1:
a.append(x)
x*=2
n/=2
return a
Advertisements
