Count of possible unique arrays after swapping elements at same index of given Arrays

0 0 7 minutes read

Given two arrays arr1[] and arr2[] with distinct elements of size N.The task is to count the total number of possible combinations after swapping elements at the same index of both the arrays such that there are no duplicates in both the arrays after performing the operation.

Examples:

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

Approach: The idea is to iterate the array for every element and make a swap, then find for swapping of the current element, how many extra swaps are needed to make the array free from duplicates. Count every different combination as a group(set) i.e for each group there are two possibilities either to make a swap or to not make a swap, so the answer will be the sum of 2 raised to the power of the number of groups. Follow the below steps to solve the problem:

Create an unordered map to store elements of both arrays in key-value pairs
Take a variable say count for the count of possible combinations and also take a vector for track of elements say visited.
Iterate over the map and check if the element is not visited, each time create a set and run a loop till the current index is not equal to i. In each iteration, insert the element of the current index of the map in the set and also update the current index. Mark all the elements as visited in the set.
After each iteration, while making groups(set), multiply the count by 2 as there are two possibilities for each group of swapping or not swapping of elements.
In the end, return the count.

Below is the implementation of the above approach:

C++

// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count possible combinations
// of arrays after swapping of elements
// such that there are no duplicates
// in the arrays
int possibleCombinations(int arr1[], int arr2[], int N)
{
    // Create an unordered_map
    unordered_map<int, int> mp;
 
    // Traverse both the arrays and
    // store the elements of arr2[]
    // in arr1[] element index in
    // the map
    for (int i = 0; i < N; i++) {
        mp[arr1[i]] = arr2[i];
    }
 
    // Take a variable for count of
    // possible combinations
    int count = 1;
 
    // Vector to keep track of already
    // swapped elements
    vector<bool> visited(N + 1, 0);
    for (int i = 1; i <= N; i++) {
 
        // If the element is not visited
        if (!visited[i]) {
 
            // Create a set
            set<int> s;
 
            // Variable to store the current index
            int curr_index = i;
 
            // Iterate a loop till curr_index
            // is equal to i
            do {
 
                // Insert the element in the set
                // of current index in map
                s.insert(mp[curr_index]);
 
                // Assign it to curr_index
                curr_index = mp[curr_index];
            } while (curr_index != i);
 
            // Iterate over the set and
            // mark element as visited
            for (auto it : s) {
                visited[it] = 1;
            }
            count *= 2;
        }
    }
    return count;
}
 
// Driver Code
int main()
{
    int arr1[] = { 3, 6, 5, 2, 1, 4, 7 };
    int arr2[] = { 1, 7, 2, 4, 3, 5, 6 };
    int N = sizeof(arr1) / sizeof(arr1[0]);
 
    cout << possibleCombinations(arr1, arr2, N);
 
    return 0;
}

Java

// Java implementation for the above approach
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
 
class GFG 
{
   
    // Function to count possible combinations
    // of arrays after swapping of elements
    // such that there are no duplicates
    // in the arrays
    public static int possibleCombinations(int arr1[], int arr2[], int N) 
    {
       
        // Create an unordered_map
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
 
        // Traverse both the arrays and
        // store the elements of arr2[]
        // in arr1[] element index in
        // the map
        for (int i = 0; i < N; i++) {
 
            mp.put(arr1[i], arr2[i]);
        }
 
        // Take a variable for count of
        // possible combinations
        int count = 1;
 
        // Vector to keep track of already
        // swapped elements
        int[] visited = new int[N + 1];
        Arrays.fill(visited, 0);
        for (int i = 1; i <= N; i++) {
 
            // If the element is not visited
            if (visited[i] <= 0) {
 
                // Create a set
                HashSet<Integer> s = new HashSet<Integer>();
 
                // Variable to store the current index
                int curr_index = i;
 
                // Iterate a loop till curr_index
                // is equal to i
                do {
 
                    // Insert the element in the set
                    // of current index in map
                    s.add(mp.get(curr_index));
 
                    // Assign it to curr_index
                    curr_index = mp.get(curr_index);
                } while (curr_index != i);
 
                // Iterate over the set and
                // mark element as visited
                for (int it : s) {
                    visited[it] = 1;
                }
                count *= 2;
            }
        }
        return count;
    }
 
    // Driver Code
    public static void main(String args[]) {
        int arr1[] = { 3, 6, 5, 2, 1, 4, 7 };
        int arr2[] = { 1, 7, 2, 4, 3, 5, 6 };
        int N = arr1.length;
 
        System.out.println(possibleCombinations(arr1, arr2, N));
    }
}
 
// This code is contributed by gfgking.

Python3

# Python3 implementation for the above approach
 
# Function to count possible combinations
# of arrays after swapping of elements
# such that there are no duplicates
# in the arrays
def possibleCombinations(arr1, arr2, N) : 
 
    # Create an unordered_map
    mp = {};
 
    # Traverse both the arrays and
    # store the elements of arr2[]
    # in arr1[] element index in
    # the map
    for i in range(N) :
        mp[arr1[i]] = arr2[i];
 
    # Take a variable for count of
    # possible combinations
    count = 1;
 
    # Vector to keep track of already
    # swapped elements
    visited = [0]*(N + 1);
     
    for i in range(1 , N + 1) :
 
        # If the element is not visited
        if (not visited[i]) :
 
            # Create a set
            s = set();
 
            # Variable to store the current index
            curr_index = i;
 
            # Iterate a loop till curr_index
            # is equal to i
            while True :
 
                # Insert the element in the set
                # of current index in map
                s.add(mp[curr_index]);
 
                # Assign it to curr_index
                curr_index = mp[curr_index];
                 
                if (curr_index == i) :
                    break
 
            # Iterate over the set and
            # mark element as visited
            for it in s :
                visited[it] = 1;
 
            count *= 2;
      
    return count;
 
# Driver Code
if __name__ == "__main__" :
 
    arr1 = [ 3, 6, 5, 2, 1, 4, 7 ];
    arr2 = [ 1, 7, 2, 4, 3, 5, 6 ];
    N = len(arr1);
 
    print(possibleCombinations(arr1, arr2, N));
 
    # This code is contributed by AnkThon

C#

// C# implementation for the above approach
using System;
using System.Collections.Generic;
class GFG {
 
    // Function to count possible combinations
    // of arrays after swapping of elements
    // such that there are no duplicates
    // in the arrays
    public static int
    possibleCombinations(int[] arr1, int[] arr2, int N)
    {
 
        // Create an unordered_map
        Dictionary<int, int> mp
            = new Dictionary<int, int>();
 
        // Traverse both the arrays and
        // store the elements of arr2[]
        // in arr1[] element index in
        // the map
        for (int i = 0; i < N; i++) {
 
            mp[arr1[i]] = arr2[i];
        }
 
        // Take a variable for count of
        // possible combinations
        int count = 1;
 
        // Vector to keep track of already
        // swapped elements
        int[] visited = new int[N + 1];
 
        for (int i = 1; i <= N; i++) {
 
            // If the element is not visited
            if (visited[i] <= 0) {
 
                // Create a set
                HashSet<int> s = new HashSet<int>();
 
                // Variable to store the current index
                int curr_index = i;
 
                // Iterate a loop till curr_index
                // is equal to i
                do {
 
                    // Insert the element in the set
                    // of current index in map
                    s.Add(mp[curr_index]);
 
                    // Assign it to curr_index
                    curr_index = mp[curr_index];
                } while (curr_index != i);
 
                // Iterate over the set and
                // mark element as visited
                foreach(int it in s) { visited[it] = 1; }
                count *= 2;
            }
        }
        return count;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int[] arr1 = { 3, 6, 5, 2, 1, 4, 7 };
        int[] arr2 = { 1, 7, 2, 4, 3, 5, 6 };
        int N = arr1.Length;
 
        Console.WriteLine(
            possibleCombinations(arr1, arr2, N));
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
 
// Javascript implementation for the above approach
 
// Function to count possible combinations
// of arrays after swapping of elements
// such that there are no duplicates
// in the arrays
function possibleCombinations(arr1, arr2, N)
{
    // Create an unordered_map
    var mp = new Map();
 
    // Traverse both the arrays and
    // store the elements of arr2[]
    // in arr1[] element index in
    // the map
    for (var i = 0; i < N; i++) {
        mp.set(arr1[i], arr2[i]);
    }
 
    // Take a variable for count of
    // possible combinations
    var count = 1;
 
    // Vector to keep track of already
    // swapped elements
    var visited = Array(N + 1).fill(false);
     
    for (var i = 1; i <= N; i++) {
 
        // If the element is not visited
        if (!visited[i]) {
 
            // Create a set
            var s = new Set();
 
            // Variable to store the current index
            var curr_index = i;
 
            // Iterate a loop till curr_index
            // is equal to i
            do {
 
                // Insert the element in the set
                // of current index in map
                s.add(mp.get(curr_index));
 
                // Assign it to curr_index
                curr_index = mp.get(curr_index);
 
            } while (curr_index != i);
 
            // Iterate over the set and
            // mark element as visited
            for (var it of [...s]) {
                visited[it] = true;
            }
            count *= 2;
        }
    }
    return count;
}
 
// Driver Code
var arr1 = [3, 6, 5, 2, 1, 4, 7];
var arr2 = [1, 7, 2, 4, 3, 5, 6];
var N = arr1.length;
document.write(possibleCombinations(arr1, arr2, N));
 
// This code is contributed by rutvik_56.
</script>

Output

Time Complexity: O(N²)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!