Сгенерируйте перестановку так, чтобы GCD всех элементов, умноженных на позицию, не был равен 1

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

Учитывая целое число N и задача состоит в том, чтобы сгенерировать перестановку чисел в диапазоне [ 1, N ] так, чтобы:

  • GCD всех элементов, умноженных на их положение (не индекс), больше 1
  • И если это невозможно вернуть -1.
  • Если возможных перестановок несколько, выведите любую из них.

Примеры:

Input: N =  8
Output: 2 1 4 3 6 5 8 7
Explanation: The elements multiplied by their positions will be 
{2*1, 1*2, 4*3, 3*4, 6*5, 5*6, 8*7, 7*8} = {2, 2, 12, 12, 30, 30, 56, 56}.
The GCD of all these numbers = 2 which is greater than 1.

Input: N = 9
Output: -1
Explanation: No permutation possible, hence return -1

Подход: Идея решения проблемы заключается в следующем:

Try to make the product of position and the number even, then in that situation GCD will be at least 2.
If there are odd number of elements then it is not possible, because odd elements are one more than possible even positions.

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

  • Храните все четные числа в одном векторе и все нечетные числа в другом векторе.
  • При создании перестановки:
    • Нажмите четное число в четном индексе (т.е. нечетное положение, потому что индексация основана на 0) и
    • Нечетное число в нечетном индексе (т.е. четное положение).

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

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

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