Kiểm tra hoán vị của số lớn có chia hết cho 8 trong Python

Cho số lớn (dưới dạng chuỗi). Kiểm tra xem có hoán vị nào của các chữ số chia hết cho 8 hay không.

Quan sát: Số chia hết cho 8 nếu 3 chữ số cuối chia hết cho 8. Do đó chỉ cần kiểm tra các hoán vị 3 chữ số có thể tạo thành từ các chữ số của số gốc.

Ví dụ: "4696984" → "Divisible by eight".

Giải thuật

• Nếu độ dài < 3: kiểm tra trực tiếp số và số đảo ngược.
• Đếm tần suất chữ số trong chuỗi.
• Duyệt các số từ 104 đến 999 chia hết cho 8 (bước 8).
• Với mỗi số, đếm tần suất 3 chữ số. Nếu tần suất ≤ tần suất trong chuỗi gốc → tồn tại hoán vị → True.

Mã ví dụ

def solve(input_num):
    if len(input_num) < 3:
        if int(input_num) % 8 == 0:
            return True
        input_num = input_num[::-1]
        if int(input_num) % 8 == 0:
            return True
        return False
    temp_arr = [0] * 10
    for ch in input_num:
        temp_arr[int(ch)] += 1
    for count in range(104, 1000, 8):
        temp = count
        occurences = [0] * 10
        occurences[temp % 10] += 1
        temp //= 10
        occurences[temp % 10] += 1
        temp //= 10
        occurences[temp % 10] += 1
        ok = True
        for d in range(10):
            if occurences[d] > temp_arr[d]:
                ok = False
                break
        if ok:
            return True
    return False

if solve("4696984"):
    print("Divisible by eight")
else:
    print("Not divisible by eight")

Đầu vào

4696984

Đầu ra

Divisible by eight