ตรวจสอบว่า N หารด้วยตัวเลขที่ประกอบด้วยตัวเลขจากเซต {A, B} ลงตัวหรือไม่ด้วย Python

สมมติมีตัวเลข n และตัวเลข a, b ต้องตรวจสอบว่าสามารถสร้างตัวเลขจาก a และ b ที่หาร n ลงตัวได้หรือไม่

เช่น Input n = 115, a = 3, b = 2 Output True เพราะ 115 หาร 23 ลงตัว (23 ประกอบด้วย 2 และ 3)

ขั้นตอนแก้ (Recursive):

• ฟังก์ชัน util(temp, a, b, n): ถ้า temp > n Return False; ถ้า n % temp == 0 Return True; Return util(temp*10+a) OR util(temp*10+b)
• Main: Return util(a) OR util(b)

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

def util(temp, a, b, n):
    if temp > n:
        return False
    if n % temp == 0:
        return True
    return util(temp * 10 + a, a, b, n) or util(temp * 10 + b, a, b, n)

def solve(n, a, b):
    return util(a, a, b, n) or util(b, a, b, n)

n = 115
a = 3
b = 2
print(solve(n, a, b))

Input

115, 2, 3

Output

True