Chương trình kiểm tra số có thể viết thành tổng giai thừa riêng biệt trong Python

Cho số dương , kiểm tra có thể viết thành tổng các giai thừa dương khác nhau hay không.

Ví dụ: → True (4! + 5! = 24 + 120 = 144).

Giải thuật (Tham lam từ giai thừa lớn nhất)

1. Tạo danh sách các giai thừa ≤ .
2. Duyệt ngược từ giai thừa lớn nhất:
   • Nếu = res[i]: .
3. Trả về .

Đúng vì giai thừa tăng rất nhanh, tham lam tối ưu.

Ví dụ minh họa

class Solution:
    def solve(self, n):
        fact = 1
        res = []
        x = 2
        while fact <= n:
            res.append(fact)
            fact = fact * x
            x += 1
        for i in range(len(res)-1, -1, -1):
            if n >= res[i]:
                n -= res[i]
        return n == 0

ob = Solution()
print(ob.solve(144))  # Output: True

Đầu vào

144

Đầu ra

True