मान लीजिए हमारे पास target नामक संख्याओं की एक सूची है। अब आइए X नामक एक सूची पर विचार करें जिसकी लंबाई दी गई सूची के समान है और X 1 से भरा है। हम निम्न ऑपरेशन को जितनी बार चाहें उतनी बार कर सकते हैं: X में किसी भी इंडेक्स i को लें और X[i] को X के वर्तमान योग पर सेट करें। अंत में जांचें कि क्या X को target में बदला जा सकता है या नहीं।
उदाहरण के लिए, यदि इनपुट target = [5, 9, 3] है, तो आउटपुट True होगा क्योंकि प्रारंभ में X = [1, 1, 1], फिर कुल योग 3 से अपडेट करें, सरणी होगी [1, 1, 3], वर्तमान योग 5 है, इसे अपडेट करें [5, 1, 3], वर्तमान योग 9, तो सूची होगी [5, 9, 3], और यह टारगेट है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- यदि nums में केवल एक तत्व है, तो
- सत्य लौटाएं जब nums में 1 हो
- q := nums के सभी संख्याओं के ऋणात्मक मान वाली एक कतार
- q को हीप बनाएं
- s := nums में सभी संख्याओं का योग
- ok := सत्य
- जब तक ok सत्य है, करें
- x := हीप से तत्व हटाएं और उसका ऋणात्मक करें
- d := s - x
- x2 := x mod d यदि d > 1 अन्यथा 1
- s := s + x2 - x
- ok := x, x2 के समान नहीं है
- x := x2
- -x को हीप q में डालें
- सत्य लौटाएं जब q में सभी तत्व -1 हों
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
उदाहरण
class Solution:
def solve(self, nums):
if len(nums) == 1:
return nums == [1]
from heapq import heapify, heappop, heappush
q = [-x for x in nums]
heapify(q)
s = sum(nums)
ok = True
while ok:
x = -heappop(q)
d = s - x
x2 = x % d if d > 1 else 1
s += x2 - x
ok = x != x2
x = x2
heappush(q, -x)
return all(x == -1 for x in q)
ob = Solution()
target = [5, 9, 3]
print(ob.solve(target))
इनपुट
[5, 9, 3]
आउटपुट
True