Максимальное количество пар в массиве с НОД больше 1 путем переупорядочения данного массива

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

Дан массив arr[] размера N . Задача состоит в том, чтобы переупорядочить arr[] и найти максимальное количество пар НОД, удовлетворяющих условиям, приведенным ниже.

  • Выберите любые два элемента массива Ai и Aj массива, где 0 <= i < j < N.
  • Рассчитайте НОД после умножения Aj на 2 подобных (Ai, 2 * Aj) , которые больше 1.

Примеры

Input: arr[] = { 3, 6 . 5, 3}
Output: 4
Explanation: Reorder array like this : { 6, 5, 3, 3 } and below are the pairs formed from arr[].
P1 = GCD( 6, 5 * 2) => (6, 10) => 2 > 1
P2 = GCD( 6, 3 * 2) => (6, 6) => 6 > 1
P3 = GCD( 6, 3 * 2) => (6, 6) => 6 > 1
P4 = GCD( 3, 3 * 2) => (3, 6) => 3 > 1

Input: arr[] = { 1, 7 }
Output: 0
Explanation: If array is order like { 7, 1 } no pair can be formed
GCD(7, 1 * 2) = > (7, 2 ), GCD(1, 7 * 2) => (1, 14) == 1

Подход: если мы заметим, что если четные элементы находятся в начальной позиции, то пары (НОД > 1) максимальны, потому что есть условие умножения arr[j] * 2 , а порядок нечетных элементов не имеет значения его количество пары всегда одинаковы. Выполните следующие шаги, чтобы решить данную проблему.

  • Инициализируйте переменную idx значением 0 .
  • Пройдитесь по массиву.
  • Если arr[i] четное, замените его на arr[idx] и увеличьте idx на 1 .
  • После прохождения всех элементов.
  • Инициализируйте переменную ans с 0 .
  • Используйте две петли сначала с i и второй с j = i + 1 .
  • Теперь, если gcd(arr[i], 2 * arr[j] * 2) > 1 , увеличьте ответ на 1 .

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

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

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