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