หาจำนวนเต็มบวกน้อยที่สุดที่หารด้วย A ลงตัวและผลรวมหลักเท่ากับ B ใน Python

สมมติว่าเรามีตัวเลข A และ B ต้องการหาจำนวนเต็มบวกน้อยที่สุด M ที่หารด้วย A ลงตัว และผลรวมหลักของ M เท่ากับ B หากไม่มีคำตอบ คืนค่า -1

เช่น A = 50, B = 2 ผลลัพธ์คือ 200 เพราะ 200 หาร 50 ลงตัว และ 2+0+0 = 2

ขั้นตอนการแก้ปัญหา (BFS)

1. สร้างคลาส Element เก็บ a (เศษ), b (ผลรวมหลัก), string (ตัวเลขเป็นสตริง)
2. ใช้คิว BFS เริ่มจาก (0, 0, "")
3. สร้างอาร์เรย์ visited ขนาด 5001x501 เพื่อป้องกันการซ้ำ
4. วนลูปจนคิวว่าง:
   • นำอิลิเมนต์แรกออกมา ถ้า a == 0 และ b == B คืนค่าตัวเลข
   • ลองต่อท้ายหลัก 0-9 คำนวณเศษใหม่และผลรวมใหม่
   • ถ้ายังไม่เกิน B และยังไม่เคยไป ให้เพิ่มเข้าคิว
5. ถ้าไม่พบ คืนค่า -1

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

visited = [[0 for _ in range(501)] for _ in range(5001)]

class Element:
    def __init__(self, a, b, string):
        self.a = a
        self.b = b
        self.string = string

def get_number(a, b):
    que = []
    elem = Element(0, 0, "")
    visited[0][0] = 1
    que.append(elem)
    while len(que) > 0:
        temp_elem = que.pop(0)
        if temp_elem.a == 0 and temp_elem.b == b:
            return int(temp_elem.string)
        for i in range(10):
            x = (temp_elem.a * 10 + i) % a
            y = temp_elem.b + i
            if y <= b and visited[x][y] == False:
                visited[x][y] = 1
                que.append(Element(x, y, temp_elem.string + str(i)))
    return -1

a, b = 50, 2
print(get_number(a, b))

อินพุต

50, 2

เอาต์พุต

200