पायथन में एक्स को शून्य करने के लिए न्यूनतम संचालन खोजने का कार्यक्रम

मान लीजिए कि हमारे पास nums नामक एक सरणी है और दूसरा मान x है। एक ऑपरेशन में, हम या तो सरणी से सबसे बाएं या सबसे दाहिने तत्व को हटा सकते हैं और x से मान घटा सकते हैं। हमें x को ठीक 0 तक कम करने के लिए आवश्यक न्यूनतम संक्रियाओं की संख्या ज्ञात करनी होगी। यदि यह संभव नहीं है तो -1 लौटाएं।

इसलिए, यदि इनपुट संख्या =[4,2,9,1,4,2,3] x =9 की तरह है, तो आउटपुट 3 होगा क्योंकि सबसे पहले हमें सबसे बाएं तत्व 4 को हटाना होगा, इसलिए सरणी होगी [2,9,1,4,2,3] और एक्स 5 होगा, फिर सबसे सही तत्व 3 को हटा दें, इसलिए सरणी [2,9,1,4,2], और एक्स =2 होगी, फिर या तो x =0 बनाने के लिए बाएं या दाएं से बाएं, और सरणी या तो [2,9,1,4] या [9,1,4,2] होगी।

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

n :=अंकों का आकार
बाएं नक्शा:=एक नया नक्शा
बाएं नक्शा[0] :=-1
बाएं:=0
मैं के लिए 0 से n -1 की सीमा में, करो
- बाएं:=बाएं + अंक[i]
- अगर लेफ्ट मैप में नहीं है, तो
  - बाएं नक्शा[बाएं] :=मैं
दाएं:=0
उत्तर :=n + 1
मैं के लिए n से 0 की सीमा में, 1 से घटाएं
- अगर मैं <एन, तो
  - दाएं:=दाएं + अंक[i]
- बाएं:=x - दाएं
- अगर लेफ्ट मैप में लेफ्ट मौजूद है, तो
  - उत्तर :=न्यूनतम उत्तर और बायां नक्शा[बाएं] + 1 + n-i
यदि उत्तर n + 1 के समान है, तो
- वापसी -1
वापसी उत्तर

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

def solve(nums, x):
   n = len(nums)

   leftMap = dict()
   leftMap[0] = -1
   left = 0
   for i in range(n):
      left += nums[i]
      if left not in leftMap:
         leftMap[left] = i

   right = 0
   ans = n + 1
   for i in range(n, -1, -1):
      if i < n:
         right += nums[i]
      left = x - right
      if left in leftMap:
         ans = min(ans, leftMap[left] + 1 + n - i)
   if ans == n + 1:
      return -1
   return ans

nums = [4,2,9,1,4,2,3]
x = 9
print(solve(nums, x))

इनपुट

[4,2,9,1,4,2,3], 9