जाँच करने के लिए कार्यक्रम हम एक सूची सूचकांक को उसके वर्तमान योग द्वारा लक्ष्य तक पहुँचने के लिए अद्यतन कर सकते हैं या नहीं अजगर में

मान लीजिए हमारे पास लक्ष्य नामक संख्याओं की एक सूची है। अब हम एक सूची X पर विचार करें जिसकी लंबाई दी गई सूची के समान है और X 1s से भरा है। हम जितनी बार चाहें निम्नलिखित ऑपरेशन कर सकते हैं:एक्स में कोई भी इंडेक्स i लें और एक्स [i] को एक्स के वर्तमान योग पर सेट करें। अंत में जांचें कि एक्स को लक्ष्य में बदला जा सकता है या नहीं।

इसलिए, यदि इनपुट लक्ष्य =[5, 9, 3] की तरह है, तो आउटपुट सही होगा क्योंकि शुरू में एक्स =[1, 1, 1], फिर इसे कुल योग 3 के साथ अपडेट करें, सरणी [1, 1] होगी , 3], वर्तमान योग 5 है, इसे अद्यतन करें [5, 1, 3], वर्तमान योग 9, इसलिए सूची [5, 9, 3] होगी, और यह लक्ष्य है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• यदि अंकों में केवल एक तत्व है, तो
  • संख्या 1 होने पर सही लौटें
• q :=सभी संख्याओं के ऋणात्मक मान वाली एक कतार
• क्यू को हीप के रूप में बनाएं
• s :=अंकों में सभी संख्याओं का योग
• ठीक है:=सच
• जबकि ठीक है सच है, करो
  • x :=हीप से एलिमेंट हटाएं और इसे नकारें
  • d :=s - x
  • x2 :=x mod d यदि d> 1 अन्यथा 1
  • s :=s + x2 - x
  • ठीक है:=x, x2 के समान नहीं है
  • x :=x2
  • ढेर q में -x डालें
• सही लौटें जब 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