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

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

সুতরাং, যদি ইনপুটটি A =50, B =2 এর মত হয়, তাহলে আউটপুট 200 হবে কারণ এটি 50 দ্বারা বিভাজ্য এবং এর অঙ্কের যোগফল =2 + 0 + 0 =2।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি উপাদান প্রকারের ধারক সংজ্ঞায়িত করুন, যাতে দুটি সংখ্যা a এবং b এবং একটি স্ট্রিং থাকে
que :=একটি নতুন তালিকা
elem :=(0, 0, ফাঁকা স্ট্রিং) সহ একটি নতুন উপাদান
পরিদর্শন করেছেন [0, 0] :=1
que এর শেষে উপাদান সন্নিবেশ করুন
যখন que এর সাইজ> 0, do
- temp_elem :=que থেকে প্রথম উপাদান মুছুন
- যদি temp_elem.a হয় 0 এবং temp_elem.b হয় b, তাহলে
  - temp_elem.string
    এর পূর্ণসংখ্যা ফেরত দিন
- আমি 0 থেকে 9 রেঞ্জের জন্য, করুন
  - x :=(temp_elem.a * 10 + i) mod a
  - y :=temp_elem.b + i
  - যদি y <=b এবং পরিদর্শন করা [x, y] মিথ্যা হয়, তাহলে
    - পরিদর্শন করেছেন [x, y] :=1
    - x, y এবং temp_elem.string concatenate i intoque
      দিয়ে নতুন উপাদান সন্নিবেশ করান
রিটার্ন -1

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

visited = [[0 for x in range(501)] for y 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(0, 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