Chương trình kiểm tra số có phải tổng các lũy thừa của 3 trong Python

Cho số n, kiểm tra xem có thể biểu diễn n dưới dạng tổng các lũy thừa của 3 khác nhau hay không. y là lũy thừa của 3 nếu tồn tại x mà y = 3^x.

Ví dụ: n = 117, đầu ra = True vì 117 = 3^4 + 3^3 + 3^2 = 81 + 27 + 9.

Giải pháp

Tham lam: trừ lần lượt các lũy thừa của 3 từ lớn đến nhỏ:

• Với i từ 16 xuống 0:
  • Nếu n >= 3^i: n := n - 3^i
• Nếu n > 0: trả về False
• Trả về True

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

def solve(n):
    for i in range(16, -1, -1):
        if n >= pow(3, i):
            n -= pow(3, i)
    if n > 0:
        return False
    return True

n = 117
print(solve(n))

Đầu vào

117

Đầu ra

True