查找一个整数X，该整数除Python中数组中仅一个元素外的所有元素的除数

假设我们有一个数字数组；我们必须找到一个数字B，该数字除以给定数组中的一个元素外，它是所有元素的除数。我们必须记住，所有要素的GCD都不是1。

因此，如果输入类似于{8，16，4，24}，则输出将为8，因为这是除4以外的所有除数。

为了解决这个问题，我们将遵循以下步骤-

• n：=数组大小

• 如果n与1相同，则

• 返回（数组[0] + 1）

• prefix：=大小为n的数组，并用0填充

• 后缀：=大小为n的数组，并用0填充

• 前缀[0]：=数组[0]

• 对于1到n范围内的i，执行

• prefix [i]：= gcd（（数组[i]和前缀[i-1]））

• 后缀[n-1]：=数组[n-1]

• 对于范围在n-2到-1的i，减1，

• 后缀[i]：=（后缀[i + 1]和array [i]的gcd）

• 对于介于0到n + 1的i

• 返回当前

• cur：=（前缀[i-1]和后缀[i + 1]的gcd）

• cur：=前缀[i-1]

• cur：=后缀[i + 1]

• cur：= 0

• 如果我等于0，那么

• 否则，当我等于n-1时，则

• 除此以外，

• 如果array [i] mod cur不等于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]

输出结果

8