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