Given two arrays A[] and B[] of size N, the task is to count the minimum number of swaps of similar indexed elements required to make one of the two given arrays equal. If it is not possible to make all elements of an array equal, then print -1.
Examples:
Input: A[] = {3, 4, 1, 3, 1, 3, 4}, B[] = {1, 3, 3, 1, 3, 4, 3}
Output: 3
Explanation:
Swapping (A[0], B[0]) modifies A[] to {1, 4, 1, 3, 1, 3, 4} and B[] to {3, 3, 3, 1, 3, 4, 3}.
Swapping (A[3], B[3]) modifies A[] to {1, 4, 1, 1, 1, 3, 4} and B[] to {3, 3, 3, 3, 3, 4, 3}.
swapping (A[5], B[5]) modifies A[] to {1, 4, 1, 1, 1, 4, 4} and B[] to {3, 3, 3, 3, 3, 3, 3}.
Since the array B[] contains only a single distinct element, the required output is 3.Input: A[] = {1, 2, 4, 1, 6, 5, 10}, B[] = {2, 3, 5, 4, 1, 8, 2}
Output: -1
Approach: The problem can be solved using Hashing. Follow the steps below to solve the problem:
- Initialize a variable, say minSwaps, to store the minimum number of swaps required such that at least one of the array contains only a single distinct value.
- Initialize another variable, say swapsRequired, to store the count of swaps required such that at least one of the array contains only a single distinct value.
- Initialize an array, say countA[], to store the frequency of each distinct element of the array A[].
- Initialize an array, say countB[], to store the frequency of each distinct element of the array B[].
- Initialize an array, say countAB[], to store the frequency of each distinct element which is present at the same indices of A[] and B[].
- Traverse both the arrays using variable i, and check if the value of (countA[i] + countB[i] – countAB[i] == N) is true or not. If found to be true, then update swapsRequired = min(countA[i], countB[i]) – countAB[i] and update minSwaps = min(minSwaps, swapsRequired).
- Finally, print the value of minSwaps.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count minimum number of swap// require such that either of the array// contain a single distinct valueint minimumNumOfSwap(int A[], int B[], int N){ // Stores largest element of // the array A[] int MaxA = *max_element(A, A + N); // Stores largest element of // the array B[] int MaxB = *max_element(B, B + N); // Stores maximum value // of (MaxA, MaxB) int M = max(MaxA, MaxB); // Store the frequency of // each distinct element of A[] int countA[M + 1] = { 0 }; // Store the frequency of // each distinct element of B[] int countB[M + 1] = { 0 }; // Store frequency of each distinct // element which is present at // same indices in A[] and B[] int equalAB[M + 1] = { 0 }; // Stores count of swaps required such // that at least one of the arrays // contain a single distinct value int swapsRequired; // Stores minimum count of swaps required // such that at least one of the arrays // contain single distinct value int minSwaps = N; // Traverse the array for (int i = 0; i < N; i++) { // Update frequency of A[i] countA[A[i]]++; // Update frequency of B[i] countB[B[i]]++; // If A[i] and B[i] are equal if (A[i] == B[i]) { // Update frequency // of A[i] and B[i] equalAB[A[i]]++; } } // Traverse each distinct // element of A[] and B[] for (int i = 1; i <= M; i++) { // If sum of frequency of i in A and B // present at different indices is N if ((countA[i] + countB[i] - equalAB[i]) == N) { // Update swapsRequired swapsRequired = min(countA[i], countB[i]) - equalAB[i]; // Update minSwaps minSwaps = min(minSwaps, swapsRequired); } } // If minSwaps is equal to N if (minSwaps == N) { return -1; } else { return minSwaps; }}// Driver Codeint main(){ int A[] = { 3, 4, 1, 3, 1, 3, 4 }; int B[] = { 1, 3, 3, 1, 3, 4, 3 }; int N = sizeof(A) / sizeof(A[0]); cout << minimumNumOfSwap(A, B, N); return 0;} |
Java
// Java program to implement // the above approach import java.util.*;public class Main{ // Function to count minimum number of swap // require such that either of the array // contain a single distinct value public static int minimumNumOfSwap(int A[], int B[], int N) { // Stores largest element of // the array A[] int MaxA = Arrays.stream(A).max().getAsInt(); // Stores largest element of // the array B[] int MaxB = Arrays.stream(B).max().getAsInt(); // Stores maximum value // of (MaxA, MaxB) int M = Math.max(MaxA, MaxB); // Store the frequency of // each distinct element of A[] int[] countA = new int[M + 1]; // Store the frequency of // each distinct element of B[] int[] countB = new int[M + 1]; // Store frequency of each distinct // element which is present at // same indices in A[] and B[] int[] equalAB = new int[M + 1]; // Stores count of swaps required such // that at least one of the arrays // contain a single distinct value int swapsRequired; // Stores minimum count of swaps required // such that at least one of the arrays // contain single distinct value int minSwaps = N; // Traverse the array for (int i = 0; i < N; i++) { // Update frequency of A[i] countA[A[i]]++; // Update frequency of B[i] countB[B[i]]++; // If A[i] and B[i] are equal if (A[i] == B[i]) { // Update frequency // of A[i] and B[i] equalAB[A[i]]++; } } // Traverse each distinct // element of A[] and B[] for (int i = 1; i <= M; i++) { // If sum of frequency of i in A and B // present at different indices is N if ((countA[i] + countB[i] - equalAB[i]) == N) { // Update swapsRequired swapsRequired = Math.min(countA[i], countB[i]) - equalAB[i]; // Update minSwaps minSwaps = Math.min(minSwaps, swapsRequired); } } // If minSwaps is equal to N if (minSwaps == N) { return -1; } else { return minSwaps; } } public static void main(String[] args) { int A[] = { 3, 4, 1, 3, 1, 3, 4 }; int B[] = { 1, 3, 3, 1, 3, 4, 3 }; int N = A.length; System.out.println(minimumNumOfSwap(A, B, N)); }}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program to implement# the above approach# Function to count minimum number of swap# require such that either of the array# contain a single distinct valuedef minimumNumOfSwap(A, B, N) : # Stores largest element of # the array A[] MaxA = max(A) # Stores largest element of # the array B[] MaxB = max(B) # Stores maximum value # of (MaxA, MaxB) M = max(MaxA, MaxB) # Store the frequency of # each distinct element of A[] countA = [0] * (M + 1) # Store the frequency of # each distinct element of B[] countB = [0] * (M + 1) # Store frequency of each distinct # element which is present at # same indices in A[] and B[] equalAB = [0] * (M + 1) # Stores count of swaps required such # that at least one of the arrays # contain a single distinct value swapsRequired = 0 # Stores minimum count of swaps required # such that at least one of the arrays # contain single distinct value minSwaps = N # Traverse the array for i in range(N) : # Update frequency of A[i] countA[A[i]] += 1 # Update frequency of B[i] countB[B[i]] += 1 # If A[i] and B[i] are equal if (A[i] == B[i]) : # Update frequency # of A[i] and B[i] equalAB[A[i]] += 1 # Traverse each distinct # element of A[] and B[] for i in range(1, M + 1) : # If sum of frequency of i in A and B # present at different indices is N if ((countA[i] + countB[i] - equalAB[i]) == N) : # Update swapsRequired swapsRequired = min(countA[i], countB[i]) - equalAB[i] # Update minSwaps minSwaps = min(minSwaps, swapsRequired) # If minSwaps is equal to N if (minSwaps == N) : return -1 else : return minSwaps# Driver codeA = [ 3, 4, 1, 3, 1, 3, 4 ]B = [ 1, 3, 3, 1, 3, 4, 3 ]N = len(A)print(minimumNumOfSwap(A, B, N))# This code is contributed by divyesh072019 |
C#
// C# program to implement // the above approach using System;using System.Linq;class GFG{ // Function to count minimum number of swap // require such that either of the array // contain a single distinct value public static int minimumNumOfSwap(int []A, int []B, int N) { // Stores largest element of // the array A[] int MaxA = A.Max(); // Stores largest element of // the array B[] int MaxB = B.Max(); // Stores maximum value // of (MaxA, MaxB) int M = Math.Max(MaxA, MaxB); // Store the frequency of // each distinct element of A[] int[] countA = new int[M + 1]; // Store the frequency of // each distinct element of B[] int[] countB = new int[M + 1]; // Store frequency of each distinct // element which is present at // same indices in A[] and B[] int[] equalAB = new int[M + 1]; // Stores count of swaps required such // that at least one of the arrays // contain a single distinct value int swapsRequired; // Stores minimum count of swaps required // such that at least one of the arrays // contain single distinct value int minSwaps = N; // Traverse the array for(int i = 0; i < N; i++) { // Update frequency of A[i] countA[A[i]]++; // Update frequency of B[i] countB[B[i]]++; // If A[i] and B[i] are equal if (A[i] == B[i]) { // Update frequency // of A[i] and B[i] equalAB[A[i]]++; } } // Traverse each distinct // element of A[] and B[] for(int i = 1; i <= M; i++) { // If sum of frequency of i in A and B // present at different indices is N if ((countA[i] + countB[i] - equalAB[i]) == N) { // Update swapsRequired swapsRequired = Math.Min(countA[i], countB[i]) - equalAB[i]; // Update minSwaps minSwaps = Math.Min(minSwaps, swapsRequired); } } // If minSwaps is equal to N if (minSwaps == N) { return -1; } else { return minSwaps; } } // Driver Codepublic static void Main(string[] args){ int []A = { 3, 4, 1, 3, 1, 3, 4 }; int []B = { 1, 3, 3, 1, 3, 4, 3 }; int N = A.Length; Console.WriteLine(minimumNumOfSwap(A, B, N));}}// This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript program to implement the above approach // Function to count minimum number of swap // require such that either of the array // contain a single distinct value function minimumNumOfSwap(A, B, N) { // Stores largest element of // the array A[] let MaxA = 0; for(let i = 0; i < A.length; i++) { MaxA = Math.max(MaxA, A[i]); } // Stores largest element of // the array B[] let MaxB = 0; for(let i = 0; i < B.length; i++) { MaxB = Math.max(MaxB, B[i]); } // Stores maximum value // of (MaxA, MaxB) let M = Math.max(MaxA, MaxB); // Store the frequency of // each distinct element of A[] let countA = new Array(M + 1); countA.fill(0); // Store the frequency of // each distinct element of B[] let countB = new Array(M + 1); countB.fill(0); // Store frequency of each distinct // element which is present at // same indices in A[] and B[] let equalAB = new Array(M + 1); equalAB.fill(0); // Stores count of swaps required such // that at least one of the arrays // contain a single distinct value let swapsRequired; // Stores minimum count of swaps required // such that at least one of the arrays // contain single distinct value let minSwaps = N; // Traverse the array for(let i = 0; i < N; i++) { // Update frequency of A[i] countA[A[i]]++; // Update frequency of B[i] countB[B[i]]++; // If A[i] and B[i] are equal if (A[i] == B[i]) { // Update frequency // of A[i] and B[i] equalAB[A[i]]++; } } // Traverse each distinct // element of A[] and B[] for(let i = 1; i <= M; i++) { // If sum of frequency of i in A and B // present at different indices is N if ((countA[i] + countB[i] - equalAB[i]) == N) { // Update swapsRequired swapsRequired = Math.min(countA[i], countB[i]) - equalAB[i]; // Update minSwaps minSwaps = Math.min(minSwaps, swapsRequired); } } // If minSwaps is equal to N if (minSwaps == N) { return -1; } else { return minSwaps; } } // Driver code let A = [ 3, 4, 1, 3, 1, 3, 4 ]; let B = [ 1, 3, 3, 1, 3, 4, 3 ]; let N = A.length; document.write(minimumNumOfSwap(A, B, N)); // This code is contributed by mukesh07.</script> |
Output:
3
Time Complexity: O(M + N), where M is the largest element in A[] and B[].
Auxiliary Space:O(M)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
