ตรวจสอบตัวเลขเป็นผลรวมของ 3 และ 7 ใน Python

ภาพรวม

โจทย์ตรวจสอบว่าตัวเลข n สามารถเขียนในรูป 3a + 7b ได้หรือไม่ โดย a,b เป็นจำนวนเต็มไม่ติดลบ (Non-negative multiples of 3 and 7)

ตัวอย่าง

n = 13 → 1×7 + 2×3 = 7 + 6 = 13 → True

อัลกอริทึม

ลอง b = 0, 7, 14, ... (เพิ่มทีละ 7) ตรวจสอบว่า n - b หาร 3 ลงตัวหรือไม่

for i in range(0, n+1, 7):
    if (n - i) % 3 == 0:
        return True
return False

โค้ด Python

class Solution:
    def solve(self, n):
        for i in range(0, n+1, 7):
            if (n - i) % 3 == 0:
                return True
        return False

ob = Solution()
print(ob.solve(13))

ทฤษฎีตัวเลข (Chicken McNugget Theorem)

สำหรับ a,b ที่ coprime ตัวเลขใหญ่ที่สุดที่เขียนไม่ได้คือ ab - a - b = 21 - 3 - 7 = 11

ดังนั้น n ≥ 12 สามารถเขียนได้เสมอ ต้องเช็คแค่ n ≤ 11

ผลลัพธ์

True