โปรแกรมตรวจสอบว่าตัวเลขเขียนเป็นผลรวมแฟกทอเรียลที่ไม่ซ้ำกันได้หรือไม่ใน Python

สมมติว่าเรามีจำนวนบวก n ต้องตรวจสอบว่าเขียนเป็นผลรวมของแฟกทอเรียล (factorial) ที่ไม่ซ้ำกันได้หรือไม่

ตัวอย่าง: n = 144 ผลลัพธ์ True เพราะ 4! + 5! = 24 + 120 = 144

ขั้นตอนการแก้ปัญหา (Greedy จากแฟกทอเรียลใหญ่ไปเล็ก)

1. สร้างรายการแฟกทอเรียล ≤ n: 1!, 2!, 3!, ...
2. วนลูปจากแฟกทอเรียลใหญ่สุดลงมาหน้าตัวเล็กสุด:
   • หาก n >= fact[i] ให้ n -= fact[i]
3. คืนค่า True หาก n == 0

ตัวอย่างโค้ด Python

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

อินพุต

144

เอาต์พุต

True