Проверьте, можно ли переставить элементы данного массива так, чтобы (arr[i] + i*K) % N = i для всех значений i в диапазоне [0, N-1]

Учитывая массив arr[] , состоящий из N положительных целых чисел и целого числа K , задача состоит в том, чтобы проверить, можно ли переставить элементы массива так, чтобы (arr[i] + i*K) % N = i для всех значений i в диапазон [0, N-1] .

Примеры:

Input: arr[] = {2, 1, 0}, K = 5
Output: Yes
Explanation: The given array can be rearranged to {0, 2, 1}. Hence the values after updation becomes {(0 + 0*5) % 3, (2 + 1*5) % 3, (1 + 2*5) % 3} => {0%3, 7%3, 11%3} => {0, 1, 2} having all elements equal to their indices in the array. 

Input: arr[] = {1, 1, 1, 1, 1}, K = 5
Output: No

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать с помощью структуры данных Set с использованием рекурсии. Ниже приведены несколько наблюдений для решения данной проблемы:

• Тот факт, что каждый элемент массива arr[i] обновляется как (arr[i] + i*K) % N . Таким образом, значения arr[i] % N и i*K % N можно вычислить независимо друг от друга.
• Если мультимножество A содержит все значения arr[i] % N , а мультимножество B содержит все значения i*K % N для всех значений i в диапазоне [0, N-1] , сгенерируйте все возможные комбинации элементов в A и B и сохранить (A[i] + B[i]) % N в наборе. Если размер результирующего множества равен N , то можно переупорядочить массив нужным образом.

Используя приведенные выше наблюдения, данная проблема может быть решена с помощью следующих шагов:

• Создайте мультимножество A , содержащее все значения arr[i] % N для всех значений i в диапазоне [0, N-1] .
• Точно так же создайте мультимножество B , содержащее все значения i*K % N для всех значений i в диапазоне [0, N-1] .
• Создайте рекурсивную функцию для перебора всех пар целых чисел в A и B , добавьте их сумму по модулю N в набор C и рекурсивно вызовите оставшиеся элементы.
• Если в какой-то момент размер набора C = N , верните true , иначе верните false .

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

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