Минимизируйте сумму массива, заменив элемент на GCD
Дан массив 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 A3 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)