Количество возможных уникальных массивов после замены элементов с тем же индексом заданных массивов

Даны два массива arr1[] и arr2[] с различными элементами размера N. Задача состоит в том, чтобы подсчитать общее количество возможных комбинаций после замены элементов с одинаковым индексом обоих массивов так, чтобы в обоих массивах не было дубликатов после выполнение операции.

Примеры:

Input: arr1[] = {1, 2, 3, 4}, arr2[] = {2, 1, 4, 3}, N = 4
Output: 4
Explanation: Possible combinations of arrays are:

• {1, 2, 3, 4} and {2, 1, 4, 3}
• {2, 1, 3, 4} and {1, 2, 4, 3}
• {1, 2, 4, 3} and {2, 1, 3, 4}
• {2, 1, 4, 3} and {1, 2, 3, 4}

The bold ones are swapped elements. So, total number of combinations = 4.

Input: arr1[] = {3, 6, 5, 2, 1, 4, 7}, arr2[] = {1, 7, 2, 4, 3, 5, 6}, N = 7
Output: 8

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

1. Создайте неупорядоченную карту для хранения элементов обоих массивов в парах ключ-значение.
2. Возьмите переменную, скажем, count для подсчета возможных комбинаций, а также возьмите вектор для отслеживания элементов, скажем, посещенных .
3. Перебирать карту и проверять, не посещался ли элемент, каждый раз создавать набор и запускать цикл до тех пор, пока текущий индекс не будет равен i . На каждой итерации вставлять элемент текущего индекса карты в набор, а также обновлять текущий индекс. Отметьте все элементы как посещенные в наборе.
4. После каждой итерации при создании групп (наборов) умножайте количество на 2 , так как для каждой группы есть две возможности замены или отсутствия замены элементов.
5. В конце верните count .
   

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

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