ปัญหา
ให้ตัวเลขใหญ่ในรูปสตริง input_num ตรวจสอบว่ามี permutation ใดที่หาร 8 ลงตัวหรือไม่
ทฤษฎีสำคัญ
ตัวเลขหาร 8 ลงตัว ⟺ 3 หลักสุดท้าย หาร 8 ลงตัว
ดังนั้น ต้องหา permutation 3 หลักจากหลักของตัวเลขที่หาร 8 ลงตัว
แนวคิดการแก้ปัญหา
- ถ้าความยาว < 3: เช็คตัวเลขโดยตรงและตัวเลขกลับหลัก
- นับความถี่หลักในตัวเลขต้นฉบับ
- วนลูปทุกจำนวน 3 หลักที่หาร 8 ลงตัว (104 ถึง 999 ก้าว 8)
- เช็คว่าความถี่หลักของจำนวนนั้น ≤ ความถี่ในตัวเลขต้นฉบับ
โค้ดตัวอย่าง
def solve(input_num):
if len(input_num) < 3:
if int(input_num) % 8 == 0:
return True
if int(input_num[::-1]) % 8 == 0:
return True
return False
from collections import Counter
freq = Counter(int(d) for d in input_num)
for num in range(104, 1000, 8):
need = Counter(int(d) for d in str(num))
if all(need[d] <= freq.get(d, 0) for d in need):
return True
return False
print("Divisible by eight" if solve("4696984") else "Not divisible by eight")
# Divisible by eight
อินพุต / เอาต์พุต
Input: 4696984 Output: Divisible by eight
