Минимизируйте сумму массива, заменив элемент на GCD

Опубликовано: 25 Февраля, 2023

Дан массив A[] длины N . Задача состоит в том, чтобы найти минимальную сумму массива (т.е. A 1 + A 2 + … + A N ), выполнив следующую операцию над заданным массивом любое количество (0 или более) раз:

  • Возьмите любые два индекса i и j, такие что 0 ≤ i, j < N , и поменяйте местами либо A i , либо A j с НОД(A i , A j ) .

Примеры:

Input: A[] = {3, 3, 9} 
Output: 9
Explanation: Choose i = 0 and j = 2 and replace A​3 with gcd(3, 9) = 3.
Now array A[]={3, 3, 3} and sum = 9 which is minimum possible sum of given array.

Input: A[] = {7, 14}
Output: 14

Подход: Чтобы решить проблему, следуйте следующей идее:

Let G = gcd(A1, A2, . . ., AN). The answer is simply N*G. because every element can be converted to be the same as G.

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

  • Вычислите НОД всех элементов массива.
  • Умножьте результат на N , чтобы получить минимальную сумму массива.

Ниже приведена реализация описанного выше подхода.

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

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