파이썬에서 배열의 정확히 하나의 요소를 제외한 모든 것의 제수인 정수 X 찾기

<시간/>

숫자 배열이 있다고 가정합니다. 주어진 배열에서 정확히 하나의 요소를 제외하고 모두의 제수인 숫자 B를 찾아야 합니다. 모든 요소의 GCD가 1이 아님을 명심해야 합니다.

따라서 입력이 {8, 16, 4, 24}와 같으면 출력은 4를 제외한 모든 제수이므로 8이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=배열의 크기
n이 1과 같으면
- return(배열[0] + 1)
접두사:=크기가 n인 배열, 0으로 채움
suffix :=크기가 n인 배열, 0으로 채움
접두사[0] :=배열[0]
1~n 범위의 i에 대해
- 접두사[i] :=(배열[i] 및 접두사[i - 1])의 gcd
접미사[n - 1] :=배열[n - 1]
n - 2 ~ -1 범위의 i에 대해 1 감소, do
- suffix[i] :=(suffix[i + 1] 및 array[i])의 gcd
0 ~ n + 1 범위의 i에 대해
- cur :=0
- i가 0과 같으면
  - cur :=접미사[i + 1]
- 그렇지 않으면 i가 n - 1과 같을 때
  - cur :=접두어[i - 1]
- 그렇지 않으면
  - cur :=gcd of (접두사[i - 1] 및 접미사[i + 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]