Tìm một số nguyên X là ước của tất cả ngoại trừ chính xác một phần tử trong một mảng bằng Python

Giả sử chúng ta có một mảng số; chúng ta phải tìm một số B là ước của tất cả ngoại trừ chính xác một phần tử trong mảng đã cho. Chúng ta phải ghi nhớ rằng GCD của tất cả các yếu tố không phải là 1.

Vì vậy, nếu đầu vào là {8, 16, 4, 24}, thì đầu ra sẽ là 8 vì đây là ước của tất cả ngoại trừ 4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng
• nếu n giống 1, thì
  • return (mảng [0] + 1)
• prefix:=một mảng có kích thước n và điền bằng 0
• hậu tố:=một mảng có kích thước n và điền bằng 0
• tiền tố [0]:=array [0]
• đối với tôi trong phạm vi từ 1 đến n, thực hiện
  • prefix [i]:=gcd of (array [i] và prefix [i - 1])
• hậu tố [n - 1]:=array [n - 1]
• đối với tôi trong phạm vi n - 2 đến -1, giảm đi 1, thực hiện
  • hậu tố [i]:=gcd của (hậu tố [i + 1] và mảng [i])
• đối với tôi trong phạm vi từ 0 đến n + 1, hãy thực hiện
  • cur:=0
  • nếu tôi giống 0, thì
    • cur:=hậu tố [i + 1]
  • ngược lại, khi tôi giống với n - 1, thì
    • cur:=tiền tố [i - 1]
  • nếu không,
    • cur:=gcd of (tiền tố [i - 1] và hậu tố [i + 1])
  • nếu mảng [i] mod cur không giống 0, thì
    • return cur
• trả về 0

Mã mẫu

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[8, 16, 4, 24]

Đầu ra

8