3348 - Suma Puteri 2

Cerință

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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse." și programul va afișa pe ecran, în ordine crescătoare, separate prin câte un spațiu, puterile lui 2 care au suma n. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

Restricții de precizări

• 1 ⩽ n ⩽ 2^31

Exemplul 1

Intrare

43

Ieșire

Datele introduse corespund restricțiilor impuse.

1

2

8

32

Rezolvare

Rezolvare ver. 1

def validare(n):
    # Verifică dacă n este format doar din cifre și dacă este între 1 și 2^31 - 1
    return n.isdigit() and 1 <= int(n) < pow(2, 31)

def descompunere_in_puteri_de_2(n):
    puteri_de_2 = []  # Lista pentru a stoca puterile de 2
    k = 0  # Contorul puterilor de 2
    while 2 ** k <= n:  # Găsește cel mai mare exponent k pentru care 2^k este mai mic sau egal cu n
        k += 1
    k -= 1  # Scade 1 din k pentru a obține cel mai mare exponent valid
    while k >= 0:  # Descompune n în sumă de puteri de 2
        if 2 ** k <= n:
            puteri_de_2.append(2 ** k)  # Adaugă puterea de 2 la lista puteri_de_2
            n -= 2 ** k  # Scade puterea de 2 din n pentru a obține restul
        k -= 1  # Scade 1 din k pentru a trece la următorul exponent mai mic
    return puteri_de_2[::-1]  # Returnează lista puterilor de 2 în ordine descrescătoare


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("\n".join(
            str(p) for p in puteri_de_2)))  # Afișează puterile de 2 separate pe linii
    else:
        print("Datele introduse nu corespund restricțiilor impuse.")