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

Cho số nguyên lớn N. Kiểm tra xem có tồn tại hoán vị của các chữ số của N sao cho số đó là palindrome và chia hết cho 3 hay không.

Ví dụ: 132213 → hoán vị 123321 là palindrome và chia hết cho 3 → "One or more permutation is a palindrome and is divisible by three".

Giải thuật

• Đếm tần suất từng chữ số và tổng chữ số.
• Nếu tổng chữ số không chia hết cho 3 → False.
• Đếm số chữ số có tần suất lẻ. Nếu > 1 → không thể tạo palindrome → trả về thông báo không.
• Ngược lại → trả về thông báo có.

Mã ví dụ

def solve(input_num):
    digit_array = [0] * 10
    input_sum = 0
    while input_num:
        input_sum += input_num % 10
        digit_array[input_num % 10] += 1
        input_num //= 10
    if input_sum % 3 != 0:
        return False
    index_odd = 0
    for i in range(10):
        if digit_array[i] % 2 != 0:
            index_odd += 1
    if index_odd > 1:
        return "No permutation is a palindrome and is divisible by three"
    else:
        return "One or more permutation is a palindrome and is divisible by three"

input_num = 132213
print(solve(input_num))

Đầu vào

132213

Đầu ra

One or more permutation is a palindrome and is divisible by three