Tìm số nguyên dương nhỏ nhất sao cho nó chia hết cho A và tổng các chữ số của nó bằng B trong Python

Giả sử ta có hai số A và B, ta phải tìm số dương nhỏ nhất M sao cho M chia hết cho A và tổng các chữ số của M bằng B. Vì vậy, nếu không có kết quả như vậy thì trả về:1.

Vì vậy, nếu đầu vào là A =50, B =2, thì đầu ra sẽ là 200 vì giá trị này chia hết cho 50 và tổng của chữ số của nó =2 + 0 + 0 =2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một vùng chứa loại phần tử, chứa hai số a và b và một chuỗi

• que:=một danh sách mới

• elem:=một phần tử mới với (0, 0, chuỗi trống)

• đã truy cập [0, 0]:=1

• chèn elem vào cuối hàng đợi

• trong khi kích thước của que> 0, do

  • temp_elem:=xóa phần tử đầu tiên khỏi hàng đợi

  • nếu temp_elem.a là 0 và temp_elem.b là b thì

    • trả về số nguyên của temp_elem.string

  • đối với tôi trong phạm vi từ 0 đến 9, hãy thực hiện

    • x:=(temp_elem.a * 10 + i) mod a

    • y:=temp_elem.b + i

    • nếu y <=b và đã truy cập [x, y] là Sai thì

      • đã truy cập [x, y]:=1

      • chèn phần tử mới với x, y và temp_elem.string nối i intoque

• trả về -1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

50, 2

Đầu ra

200