समस्या विवरण
संख्याओं की एक सरणी दी गई है, एक संख्या B ढूंढें जो सरणी के सभी तत्वों का भाजक हो सिवाय ठीक एक तत्व के। ध्यान रखें कि सभी तत्वों का GCD 1 नहीं है।
उदाहरण
इनपुट: [8, 16, 4, 24]
आउटपुट: 8 (8, 16, 24 का भाजक है, 4 का नहीं)
एल्गोरिदम (प्रीफिक्स/सफिक्स GCD)
n = len(array); यदि 1 तोarray[0]+1वापस करेंprefix[i]= 0 से i तक GCDsuffix[i]= i से n-1 तक GCD- प्रत्येक इंडेक्स
iके लिए:cur = gcd(prefix[i-1], suffix[i+1])(किनारों के लिए समायोजन)- यदि
array[i] % cur != 0:curवापस करें
- 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(n):
if i == 0:
cur = suffix[1]
elif i == n-1:
cur = prefix[n-2]
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]
आउटपुट
8