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

मान लीजिए कि हमारे पास एक और मान सीमा की लंबाई की एक सरणी संख्या है। एक चाल में, हम अंकों से किसी भी मान को 1 और सीमा के बीच के किसी अन्य मान से बदल सकते हैं, जिसमें शामिल हैं। सरणी को पूरक कहा जाता है यदि सभी सूचकांकों के लिए i, nums[i] + nums[n-1-i] समान संख्या के बराबर हो। इसलिए हमें अंकों को पूरक बनाने के लिए आवश्यक चालों की न्यूनतम संख्या ज्ञात करनी होगी।

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

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

• n :=अंकों का आकार
• मध्य :=n/2 का भागफल
• zero_moves :=पूर्णांक प्रकार मान का एक खाली नक्शा
• शुरू करें:=आकार की एक सरणी (2 * सीमा + 1), और 0 से भरें
• अंत:=आकार की एक सरणी (2 * सीमा + 1), और 0 से भरें
• res :=अनंत
• मैं के लिए 0 से मध्य -1 की सीमा में, करो
  • x :=nums[i]
  • y :=nums[n - 1 - i]
  • zero_moves[x + y] :=Zero_moves[x + y] + 1
  • प्रारंभ बढ़ाएं[1 + न्यूनतम x, y] 1 तक
  • अंत बढ़ाएं[सीमा + अधिकतम x, y] 1 तक
• अंतराल:=0
• सीमा 2 से सीमा*2 तक के लक्ष्य के लिए
  • अंतराल:=अंतराल + प्रारंभ[लक्ष्य]
  • लागत:=2 *(मध्य-अंतराल) + अंतराल - शून्य_मूव्स[लक्ष्य]
  • res :=न्यूनतम रेस और लागत
  • अंतराल:=अंतराल - अंत[लक्ष्य]
• रिटर्न रेस

उदाहरण

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

from collections import defaultdict
def solve(nums, limit):
   n = len(nums)
   mid = n // 2

   zero_moves = defaultdict(int)

   start = [0] * (2 * limit + 1)
   end = [0] * (2 * limit + 1)
   res = float('inf')
   for i in range(mid):
      x = nums[i]
      y = nums[n - 1 - i]
      zero_moves[x + y] += 1
      start[min(x, y) + 1] += 1
      end[max(x, y) + limit] += 1

   intervals = 0
   for target in range(2, limit * 2 + 1):
      intervals += start[target]
      cost = 2 * (mid - intervals) + intervals - zero_moves[target]
      res = min(res, cost)
      intervals -= end[target]
   return res

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

इनपुट

[1,4,2,3], 4

आउटपुट

1