Вычислить НОД всех попарных сумм заданных двух массивов

Опубликовано: 19 Сентября, 2022

Учитывая два массива A[] и B[] размера N и M , вычислить НОД всех попарных сумм (A[i]+B[j]) 1<=i<=N и 1<=j<=M.

Примеры:

Input: A[] = {1, 7, 25, 55}, B[] = {1, 3, 5}
Output: 2
Explanation: The GCD of all pairwise sum of (A[i]+B[j]) is equals to 
GCD(1+1, 1+3, 1+5, 7+1, 7+3, 7+5, 25+1, 25+3, 25+5, 55+1, 55+3, 55+5)
GCD(2, 4, 6, 8, 10, 12, 26, 28, 30, 56, 58, 60) = 2

Input: A[] = {8, 16, 20}, B[] = {12, 24}
Output: 4 

Наивный подход : простой подход к этой проблеме состоит в том, чтобы вычислить все попарные суммы, а затем вычислить их НОД.

Ниже приведена реализация этого подхода.

Временная сложность : O(N*M)
Вспомогательное пространство : O(N)

Эффективный подход : проблема может быть решена эффективно на основе следующего математического наблюдения:

Наблюдение :

  • By Euclidean algorithm it can be said that GCD( a, b) =  GCD(a-b, b) where(a>b) .   
  • Then for any j
    GCD(A[0] + B[j], A[1] + B[j], . . ., A[N-1] + B[j]) = GCD(A[0]+B[j], A[1]-A[0], A[2]-A[0], . . ., A[N]-A[0]). 
    The term GCD(A[1]-A[0], A[2]-A[0], . . ., A[N]-A[0]) is common for all j from 0 to M-1 (say this is X)
  • This leaves us with only the elements of type (A[0] + B[j]) for which will calculate their GCD and will get the desired GCD upon calculating their GCD with X

Выполните следующие шаги, чтобы решить эту проблему:

  • Сначала отсортируйте оба массива.
  • Затем выполните итерацию от i = 1 до N-1 и вычислите НОД всех пар A[i] -A[0] (скажем, X ).
  • Затем выполните итерацию от i = 1 до M-1 и вычислите НОД всех пар A[0] +B[i] (скажем, Y ).
  • Верните окончательный ответ, который является НОД (X и Y).

Ниже приведена реализация этого подхода.

Временная сложность : O(N*logN + M*logM)
Вспомогательное пространство : O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ