एक पूर्णांक एक्स खोजें जो पायथन में एक सरणी में बिल्कुल एक तत्व को छोड़कर सभी का विभाजक है

मान लीजिए हमारे पास संख्याओं की एक सरणी है; हमें एक संख्या B ज्ञात करनी है जो दिए गए सरणी में केवल एक तत्व को छोड़कर सभी का भाजक है। हमें यह ध्यान रखना होगा कि सभी तत्वों का GCD 1 नहीं है।

इसलिए, यदि इनपुट {8, 16, 4, 24} जैसा है, तो आउटपुट 8 होगा क्योंकि यह 4 को छोड़कर सभी का भाजक है।

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

n :=सरणी का आकार
यदि n 1 के समान है, तो
- वापसी(सरणी[0] + 1)
उपसर्ग :=आकार n की एक सरणी, और 0 से भरें
प्रत्यय:=आकार n की एक सरणी, और 0 से भरें
उपसर्ग[0] :=सरणी[0]
1 से n की श्रेणी में i के लिए, करें
- उपसर्ग[i] :=gcd of (सरणी[i] और उपसर्ग[i - 1])
प्रत्यय [n - 1] :=सरणी[n - 1]
मैं के लिए n - 2 से -1 की श्रेणी में, 1 से घटाएं
- प्रत्यय[i] :=gcd of (प्रत्यय[i + 1] और सरणी[i])
मैं के लिए 0 से n + 1 की सीमा में, करो
- कर :=0
- यदि मैं 0 के समान है, तो
  - cur :=प्रत्यय[i + 1]
- अन्यथा जब मैं n-1 के समान हो, तो
  - cur :=उपसर्ग[i - 1]
- अन्यथा,
  - cur :=gcd of (उपसर्ग[i - 1] और प्रत्यय[i + 1])
- यदि सरणी [i] मॉड वक्र 0 के समान नहीं है, तो
  - वापसी वक्र
वापसी 0

उदाहरण कोड

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

from math import gcd
def getDivisor(array):
   n = len(array)
   if (n == 1):
      return (array[0] + 1)
   prefix = [0] * n
   suffix = [0] * n
   prefix[0] = array[0]
   for i in range(1, n):
      prefix[i] = gcd(array[i], prefix[i - 1])
   suffix[n - 1] = array[n - 1]
   for i in range(n - 2, -1, -1):
      suffix[i] = gcd(suffix[i + 1], array[i])
   for i in range(0, n + 1):
      cur = 0
      if (i == 0):
         cur = suffix[i + 1]
      elif (i == n - 1):
         cur = prefix[i - 1]
      else:
         cur = gcd(prefix[i - 1], suffix[i + 1])
      if (array[i] % cur != 0):
         return cur
   return 0;
array = [8, 16, 4, 24]
print(getDivisor(array))

इनपुट

[8, 16, 4, 24]