在 Python 中查找一个整数 X，它是数组中除一个元素外所有元素的除数

pythonserver side programmingprogramming更新于 2025/10/17 22:36:17

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

因此，如果输入为 {8, 16, 4, 24}，则输出将为 8，因为这是除 4 之外的所有元素的除数。

要解决这个问题，我们将遵循以下步骤 −

n := 数组大小
如果 n 与 1 相同，则
- return(array[0] + 1)
前缀 := 大小为 n 的数组，并用 0 填充
后缀 := 大小为 n 的数组，并用 0 填充
前缀[0] := 数组[0]
对于范围为 1 到 n 的 i，执行
- prefix[i] := (array[i] and prefix[i - 1]) 的 gcd
suffix[n - 1] := array[n - 1]
对于 n - 2 到 -1 范围内的 i，减少 1，执行
- suffix[i] := (suffix[i + 1] and array[i]) 的 gcd
对于 0 到 n + 1 范围内的 i，执行
- cur := 0
- 如果 i 与 0 相同，则
  - cur := suffix[i + 1]
- 否则，当 i 与 n - 相同时1，则
  - cur := prefix[i - 1]
- 否则，
  - cur := (prefix[i - 1] and suffix[i + 1]) 的 gcd
- 如果 array[i] mod 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(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))