3348 - SumaPuteri2

Cerința

Se dă un număr natural n. Descompuneți numărul n ca sumă de puteri ale lui 2.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran, în ordine crescătoare, separate prin câte un spațiu, puterile lui 2 care au suma n.

Restricții și precizări

1 ≤ n < 231

Exemplu

Intrare

43

Iesire

1 2 8 32

Rezolvare

Rezolvare ver. 1

def validare(n):
    return n.isdigit() and 1 <= int(n) < 231


def descompunere_in_puteri_de_2(n):
    puteri_de_2 = []
    k = 0
    while 2 ** k <= n:
        k += 1
    k -= 1
    while k >= 0:
        if 2 ** k <= n:
            puteri_de_2.append(2 ** k)
            n -= 2 ** k
        k -= 1
    return puteri_de_2[::-1]


if __name__ == '__main__':
    n = input("Introduceți numărul n: ")
    if validare(n):
        n = int(n)
        print("Datele introduse corespund restricțiilor impuse.")
        puteri_de_2 = descompunere_in_puteri_de_2(n)
        print("{}".format(" ".join(
            str(p) for p in puteri_de_2)))
    else:
        print("Datele introduse nu corespund restricțiilor impuse.")