Given two arrays arr[] and brr[] of length N, the task is to find the minimum number of swaps of the same indexed elements required such an element occurs at least half of the indices in the array arr[], i.e. Majority element. If it is not possible to obtain such an arrangement, then print “-1”.
Examples:
Input: arr[] = {3, 2, 1, 4, 9}, brr[] = {5, 5, 3, 5, 3}
Output: 2
Explanation:
Following are the swaps required:
Swap 1: Swapping arr[1] and brr[1] modifies arr[] to {3, 2, 3, 4, 9} and brr[] to {5, 5, 1, 5, 3}.
Swap 2: Swapping arr[5] and brr[5] modifies arr[] to {3, 2, 3, 4, 3} and brr[] to {5, 5, 1, 5, 9}.
Therefore, the total number of swaps required is 2.Input: arr[] = {2, 4, 2}, brr[] = {1, 2, 9}
Output: 0
Approach: Follow the steps below to solve the above problem:
- Initialize a variable res as INT_MAX that stores the minimum swap required.
- Find the frequency count of arrays a[] and b[] elements using hashing and store it in the map A and B respectively.
- Create an array, crr[] of size 2*N to store all elements from the array arr[] and brr[].
- Traverse the array crr[] using the variable i and do the following:
- If the frequency of crr[i] in map A is at least N/2 then the minimum swap required is 0 and break out of the loop and print 0.
- If the sum of the frequency of crr[i] in maps A and B is at least N/2 then update res to the minimum of res and (N/2 – A[crr[i]]).
- After the above steps, if the value of res is still INT_MAX, then print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that counts the minimum // number of swaps required to make // half of the element same in a[] int minMoves( int a[], int b[], int n) { // Stores frequency of elements in a[] // Stores frequency of elements in b[] unordered_map< int , int > A, B; // Stores all elements from both arrays vector< int > c; // Find the maximum occurrence // required int maxOccur = ceil ( floor (n) / (2 * 1.0)); for ( int i = 0; i < n; ++i) { c.push_back(a[i]); c.push_back(b[i]); A[a[i]]++; // If a[i] == b[i], then no need // of incrementing in map B if (b[i] != a[i]) { B[b[i]]++; } } // Store the minimum number of swaps int res = INT_MAX; for ( int i = 0; i < c.size(); ++i) { // Frequency of c[i] in array a int x = A]; // Frequency of c[i] in array b int y = B]; // Check the frequency condition if ((x + y) >= maxOccur) { // if c[i] is present at // least half times in array // a[], then 0 swaps required if (x >= maxOccur) { return 0; } // maxOccur - x is the count // of swaps needed to make // c[i] the majority element else { res = min(res, maxOccur - x); } } } // If not possible if (res == INT_MAX) { return -1; } // Otherwise else return res; } // Driver Code int main() { // Given arrays a[] and b[] int arr[] = { 3, 2, 1, 4, 9 }; int brr[] = { 5, 5, 3, 5, 3 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call cout << minMoves(arr, brr, N); return 0; } |
Java
// Java program for the // above approach import java.util.*; class Main{ // Function that counts the minimum // number of swaps required to make // half of the element same in a[] public static int minMoves( int a[], int b[], int n) { // Stores frequency of elements // in a[] // Stores frequency of elements // in b[] HashMap<Integer, Integer> A = new HashMap<>(); HashMap<Integer, Integer> B = new HashMap<>(); // Stores all elements from // both arrays Vector<Integer> c = new Vector<Integer>(); // Find the maximum occurrence // required int maxOccur = ( int )Math.ceil( ( int )Math.floor(n) / ( 2 * 1.0 )); for ( int i = 0 ; i < n; ++i) { c.add(a[i]); c.add(b[i]); if (A.containsKey(a[i])) { A.replace(a[i], A.get(a[i]) + 1 ); } else { A.put(a[i], 1 ); } // If a[i] == b[i], then no need // of incrementing in map B if (b[i] != a[i]) { if (B.containsKey(b[i])) { B.replace(b[i], B.get(b[i]) + 1 ); } else { B.put(b[i], 1 ); } } } // Store the minimum number // of swaps int res = Integer.MAX_VALUE; for ( int i = 0 ; i < c.size(); ++i) { // Frequency of c[i] in array a int x = 0 ; if (A.containsKey(c.get(i))) { x = A.get(c.get(i)); } // Frequency of c[i] in array b int y = 0 ; if (B.containsKey(c.get(i))) { y = B.get(c.get(i)); } // Check the frequency // condition if ((x + y) >= maxOccur) { // if c[i] is present at // least half times in array // a[], then 0 swaps required if (x >= maxOccur) { return 0 ; } // maxOccur - x is the count // of swaps needed to make // c[i] the majority element else { res = Math.min(res, maxOccur - x); } } } // If not possible if (res == Integer.MAX_VALUE) { return - 1 ; } // Otherwise else return res; } // Driver code public static void main(String[] args) { // Given arrays a[] and b[] int arr[] = { 3 , 2 , 1 , 4 , 9 }; int brr[] = { 5 , 5 , 3 , 5 , 3 }; int N = arr.length; // Function Call System.out.println(minMoves(arr, brr, N)); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for the above approach from math import ceil, floor import sys # Function that counts the minimum # number of swaps required to make # half of the element same in a[] def minMoves(a, b, n): # Stores frequency of elements in a[] # Stores frequency of elements in b[] A, B = {}, {} # Stores all elements from both arrays c = [] # Find the maximum occurrence # required maxOccur = ceil(floor(n) / ( 2 * 1.0 )) for i in range (n): c.append(a[i]) c.append(b[i]) A[a[i]] = A.get(a[i], 0 ) + 1 # If a[i] == b[i], then no need # of incrementing in map B if (b[i] ! = a[i]): B[b[i]] = B.get(b[i], 0 ) + 1 # Store the minimum number of swaps res = sys.maxsize for i in range ( len (c)): # Frequency of c[i] in array a x, y = 0 , 0 if c[i] in A: x = A] # Frequency of c[i] in array b if c[i] in B: y = B] # Check the frequency condition if ((x + y) > = maxOccur): # If c[i] is present at # least half times in array # a[], then 0 swaps required if (x > = maxOccur): return 0 # maxOccur - x is the count # of swaps needed to make # c[i] the majority element else : res = min (res, maxOccur - x) # If not possible if (res = = sys.maxsize): return - 1 # Otherwise else : return res # Driver Code if __name__ = = '__main__' : # Given arrays a[] and b[] arr = [ 3 , 2 , 1 , 4 , 9 ] brr = [ 5 , 5 , 3 , 5 , 3 ] N = len (arr) # Function Call print (minMoves(arr, brr, N)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG{ // Function that counts the minimum // number of swaps required to make // half of the element same in []a public static int minMoves( int []a, int []b, int n) { // Stores frequency of elements // in []a // Stores frequency of elements // in []b Dictionary< int , int > A = new Dictionary< int , int >(); Dictionary< int , int > B = new Dictionary< int , int >(); // Stores all elements from // both arrays List< int > c = new List< int >(); // Find the maximum occurrence // required int maxOccur = ( int )(Math.Ceiling( ( int )(Math.Floor( ( double )n)) / (2 * 1.0))); for ( int i = 0; i < n; ++i) { c.Add(a[i]); c.Add(b[i]); if (A.ContainsKey(a[i])) { A[a[i]] = A[a[i]] + 1; } else { A.Add(a[i], 1); } // If a[i] == b[i], then no need // of incrementing in map B if (b[i] != a[i]) { if (B.ContainsKey(b[i])) { B[b[i]]++; } else { B.Add(b[i], 1); } } } // Store the minimum number // of swaps int res = int .MaxValue; for ( int i = 0; i < c.Count; ++i) { // Frequency of c[i] in array a int x = 0; if (A.ContainsKey(c[i])) { x = A]; } // Frequency of c[i] in array b int y = 0; if (B.ContainsKey(c[i])) { y = B]; } // Check the frequency // condition if ((x + y) >= maxOccur) { // If c[i] is present at // least half times in array // []a, then 0 swaps required if (x >= maxOccur) { return 0; } // maxOccur - x is the count // of swaps needed to make // c[i] the majority element else { res = Math.Min(res, maxOccur - x); } } } // If not possible if (res == int .MaxValue) { return -1; } // Otherwise else return res; } // Driver code public static void Main(String[] args) { // Given arrays []a and []b int []arr = { 3, 2, 1, 4, 9 }; int []brr = { 5, 5, 3, 5, 3 }; int N = arr.Length; // Function Call Console.WriteLine(minMoves(arr, brr, N)); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program for the above approach // Function that counts the minimum // number of swaps required to make // half of the element same in a[] function minMoves(a, b, n) { // Stores frequency of elements in a[] // Stores frequency of elements in b[] var A = new Map(), B = new Map(); // Stores all elements from both arrays var c = []; // Find the maximum occurrence // required var maxOccur = Math.ceil(Math.floor(n) / (2 * 1.0)); for ( var i = 0; i < n; ++i) { c.push(a[i]); c.push(b[i]); if (A.has(a[i])) { A.set(a[i], A.get(a[i])+1); } else { A.set(a[i], 1); } // If a[i] == b[i], then no need // of incrementing in map B if (b[i] != a[i]) { if (B.has(b[i])) { B.set(b[i], B.get(b[i])+1); } else { B.set(b[i], 1); } } } // Store the minimum number of swaps var res = 1000000000; for ( var i = 0; i < c.length; ++i) { // Frequency of c[i] in array a var x = A.get(c[i]); // Frequency of c[i] in array b var y = B.get(c[i]); // Check the frequency condition if ((x + y) >= maxOccur) { // if c[i] is present at // least half times in array // a[], then 0 swaps required if (x >= maxOccur) { return 0; } // maxOccur - x is the count // of swaps needed to make // c[i] the majority element else { res = Math.min(res, maxOccur - x); } } } // If not possible if (res == 1000000000) { return -1; } // Otherwise else return res; } // Driver Code // Given arrays a[] and b[] var arr = [3, 2, 1, 4, 9]; var brr = [5, 5, 3, 5, 3]; var N = arr.length; // Function Call document.write( minMoves(arr, brr, N)); </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!