Найдите перестановку, которая генерирует лексикографически самый большой массив префиксов GCD

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

Для заданного массива A[] размера N найдите такую перестановку массива A, что массив B[] , образованный путем взятия НОД префиксов массива A, является лексикографически наибольшим среди всех возможных массивов. Выведите перестановку A, а также B.

Примечание. Если возможно несколько ответов, выведите любой из них.

Примеры:

Input: A[] = {2, 1, 4, 8, 16, 32, 5}
Output: A[] = {32, 16, 8, 4, 2, 5, 1}, B = {32, 16, 8, 4, 2, 1, 1}
Explanation: B[] = {gcd(32),  gcd(32, 16),  gcd(32, 16, 8), gcd(32, 16, 8, 4),  
gcd(32, 16, 8, 4, 2), gcd(32, 16, 8, 4, 2, 1, 5), gcd(32, 16, 8, 4, 2, 1, 5)}  

Input: A[] =  {5, 20, 21, 5, 17}
Output: A[] = {21, 20, 17, 5, 5 }, B[] = {21, 1, 1, 1, 1}

Наивный подход:

Iterate through all the permutations of A, find the gcd of the prefix of the array then sort all the arrays and print the greatest lexicographically array of gcd of the prefix.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Создайте перестановку для массива.
    • Переберите массив и сгенерируйте массив B[] из этой перестановки.
    • Проверьте, является ли он лексикографически лучшим, и обновите его соответствующим образом.
  • Возвратите перестановку, которая генерирует лексикографически самый большой B[] .

Ниже приведен код вышеупомянутого подхода:

Временная сложность: O(N * N!), N! чтобы найти перестановку и N для повторения каждой перестановки.
Вспомогательное пространство: O(1)

Эффективный подход:

Iterate all the elements and for each element:

  • Traverse  all the other elements and find which element gives the greatest GCD among them.
  • That will the be next element because it will generate a greater GCD for the B[] array. 

Continue this process till the array is built.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Первоначально сохраните GCD = 0 (чтобы получить максимальный gcd на следующем шаге, потому что gcd (0, x) = x)
  • Переход от i = 0 к N :
    • Итерируйте от j = 0 до N .
      • Если НОД A[j] с предыдущим НОД является максимальным, обновите значение НОД.
    • Поместите A[j] и максимальный НОД в результирующие массивы.
  • Когда итерация закончится, верните результирующие массивы.

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

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

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