CodeFights – Powers Of Two

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s