পাইথনে A-দ্বারা বিভাজ্য এবং অঙ্কের যোগফল B হয় এমন ন্যূনতম ধনাত্মক পূর্ণসংখ্যা

দুটি সংখ্যা A এবং B দেওয়া থাকলে, ন্যূনতম ধনাত্মক সংখ্যা M খুঁজে বের করতে হবে যাতে M, A-দ্বারা বিভাজ্য হয় এবং M-এর অঙ্কগুলোর যোগফল B-এর সমান হয়। যদি এমন কোনো সংখ্যা না থাকে, তবে -1 ফেরত দিন।

উদাহরণ

ইনপুট: A = 50, B = 2

আউটপুট: 200 (কারণ 200 ÷ 50 = 4 এবং 2+0+0 = 2)

সমাধানের পদ্ধতি

BFS (Breadth-First Search) ব্যবহার করে সমাধান করা হয়।
প্রতিটি অবস্থা (state) হিসেবে (অবশিষ্ট, অঙ্কের_যোগফল, সংখ্যা_স্ট্রিং) রাখা হয়।
শুরুতে (0, 0, "") থেকে শুরু করা হয়।
প্রতিটি ধাপে ০ থেকে ৯ পর্যন্ত অঙ্ক যোগ করে নতুন অবস্থা তৈরি করা হয়।
যদি কোনো অবস্থায় অবশিষ্ট ০ এবং অঙ্কের যোগফল B হয়, তবে সেটিই উত্তর।
ভিজিটেড অ্যারের মাধ্যমে পুনরাবৃত্তি এড়ানো হয়।

পাইথন কোড

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