मान लीजिए हमारे पास दो संख्याएं A और B हैं, हमें न्यूनतम धनात्मक संख्या M ढूंढनी है ताकि M, A से विभाज्य हो और M के अंकों का योग B के समान हो। यदि ऐसा कोई परिणाम नहीं है, तो -1 लौटाएं।
तो, यदि इनपुट A = 50, B = 2 जैसा है, तो आउटपुट 200 होगा क्योंकि यह 50 से विभाज्य है और इसके अंकों का योग = 2 + 0 + 0 = 2 है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
एक तत्व प्रकार का कंटेनर परिभाषित करें, जिसमें दो संख्याएं a और b और एक स्ट्रिंग हो
que := एक नई सूची
elem := (0, 0, खाली स्ट्रिंग) के साथ एक नया तत्व
visited[0, 0] := 1
que के अंत में elem डालें
जब que का आकार > 0 हो, करें:
temp_elem := que से पहला तत्व हटाएं
यदि temp_elem.a 0 है और temp_elem.b, b है, तो:
temp_elem.string का पूर्णांक लौटाएं
i को 0 से 9 तक के लिए, करें:
x := (temp_elem.a * 10 + i) mod a
y := temp_elem.b + i
यदि y <= b और visited[x, y] गलत है, तो:
visited[x, y] := 1
x, y और temp_elem.string को i के साथ जोड़कर que में नया तत्व डालें
-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
आउटपुट
200
