Подсчитайте перестановки первых N натуральных чисел, сумма соседних элементов которых равна полному квадрату.

Для заданного положительного целого числа N задача состоит в том, чтобы найти количество уникальных перестановок первых N натуральных чисел, у которых сумма соседних элементов равна полному квадрату.

Примеры:

Input: N = 17
Output: 2
Explanation:
Following permutations have sum of adjacent elements equal to a perfect square:

1. {17, 8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16}
2. {16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8, 17}

Therefore, count of such permutations is 2.

Input: N = 13
Output: 0

Подход: Данная проблема может быть решена с использованием концепций графа. Выполните следующие шаги, чтобы решить проблему:

• Перечислите все совершенные квадратные числа до (2*N – 1) , которые можно получить, сложив любые два положительных целых числа.
• Представьте граф как представление списка смежности таким образом, что если сумма двух чисел X и Y является полным квадратом, то добавьте ребро от узла X к узлу Y .
• Подсчитайте количество узлов в графе, степень входа которых равна 1, и сохраните его в переменной X .
• Теперь количество перестановок можно рассчитать в соответствии со следующими условиями:
  • Если значение X равно 0 , то всего возможно N перестановок. Следовательно, выведите N как результат.
  • Если значение X равно 1 или 2 , то всего возможны 2 перестановки. Следовательно, выведите 2 в качестве результата.
  • В противном случае таких перестановок, удовлетворяющих заданным критериям, не существует. Следовательно, выведите 0 в качестве результата.

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

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