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

Дан массив arr[] размера N. Задача состоит в том, чтобы найти минимальное количество свопов, необходимых для переупорядочивания массива таким образом, чтобы все элементы с простым индексом были простыми . Если задача не может быть достигнута, выведите « -1 ». “

Примеры:

Input:  N = 5, arr[] = {1, 2, 3, 4, 5}
Output: 0
Explanation: All the prime indices {2, 3, 5} (one-based indexing) have prime elements present on them. Therefore, minimum swaps required is 0.

Input:  N = 5, arr[] = {2, 7, 8, 5, 13}
Output: 1
Explanation: swap 8 and 5 once, to get all the prime numbers at prime indices.

Подход: Задачу можно решить с помощью Решета Эратосфена.

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

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

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