Given two arrays arr1[] and arr2[] of size N, the task is to count the minimum number of swaps of same-indexed elements from both the arrays arr1[] and arr2[] required to make the sum of all elements of both the arrays even. If it is not possible, then print “-1”.
Examples:
Input: arr1[] = {1, 4, 2, 3}, arr2[] = {2, 3, 4, 1}
Output: 0
Explanation: Sum of all elements of arr1[] and arr2[] is 10 and 10 respectively, which is already even. Therefore, the count of operations required is 0.Input: arr1[] = {11, 14, 20, 2}, arr2[] = {5, 9, 6, 3}
Output: 1
Explanation: Sum of all elements of arr1[] and arr2[] is 37 and 23 respectively. Swapping arr1[1]( = 14) and arr2[1]( = 9) makes the sum of arr1[] and arr2[], 32 and 28 respectively. Therefore, the count of operations required is 1.
Approach: The idea is based on the following observations assuming that the sum of the array arr1[] is sumArr1 and that of arr2[] is sumArr2.
- If sumArr1 is even and sumArr2 is even: No swaps required.
- If sumArr1 is odd and sumArr2 is odd: Find a pair of same-indexed elements whose sum is odd and swap them. Such a pair contains one even number and an odd number. Swapping them increases the sum of one array by 1 and decreases that of the other array by 1. Therefore, sum of both the arrays is even.
- If sumArr1 is even and sumArr2 is odd: Not possible to make sum of both the arrays even.
- If sumArr1 is odd and sumArr2 is even: Not possible to make sum of both the arrays even.
Follow the steps below to solve the problem:
- Initialize sumArr1 = 0 and sumArr2 = 0 to store the sum of arr1[] and arr2[] respectively.
- If sumArr1 and sumArr2 are both found to be even, then print 0.
- If sumArr1 and sumArr2 are both found to be odd, then iterate a loop over the range [0, N – 1] and check if there exists any corresponding pair whose sum is odd or not. If any such pair is found, then print 1.
- Otherwise, for all other cases, 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 to count the minimum swaps// of same-indexed elements from arrays// arr1[] and arr2[] required to make// the sum of both the arrays evenvoid minimumSwaps(int arr1[], int arr2[], int n){ // Store the sum of elements of // the array arr1 and arr2 respectively int sumArr1 = 0, sumArr2 = 0; // Store the array sum of both the arrays for (int i = 0; i < n; ++i) { sumArr1 += arr1[i]; sumArr2 += arr2[i]; } // If both sumArr1 and sumArr2 // are even, print 0 and return if (sumArr1 % 2 == 0 && sumArr2 % 2 == 0) { cout << 0; return; } // If both sumArr1 and sumArr2 // are odd and check for a pair // with sum odd sum if (sumArr1 % 2 != 0 && sumArr2 % 2 != 0) { // Stores if a pair with // odd sum exists or not int flag = -1; // Traverse the array for (int i = 0; i < n; ++i) { // If a pair exists with odd // sum, set flag = 1 if ((arr1[i] + arr2[i]) % 2 == 1){ flag = 1; break; } } // Print the answer and return cout << flag; return; } // For all other cases, print -1 cout << -1;}// Driver Codeint main(){ int arr1[] = { 11, 14, 20, 2 }; int arr2[] = { 5, 9, 6, 3 }; int N = sizeof(arr1) / sizeof(arr1[0]); // Function Call minimumSwaps(arr1, arr2, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to count the minimum swaps// of same-indexed elements from arrays// arr1[] and arr2[] required to make// the sum of both the arrays evenstatic void minimumSwaps(int arr1[], int arr2[], int n){ // Store the sum of elements of // the array arr1 and arr2 respectively int sumArr1 = 0, sumArr2 = 0; // Store the array sum of both the arrays for(int i = 0; i < n; ++i) { sumArr1 += arr1[i]; sumArr2 += arr2[i]; } // If both sumArr1 and sumArr2 // are even, print 0 and return if (sumArr1 % 2 == 0 && sumArr2 % 2 == 0) { System.out.print(0); return; } // If both sumArr1 and sumArr2 // are odd and check for a pair // with sum odd sum if (sumArr1 % 2 != 0 && sumArr2 % 2 != 0) { // Stores if a pair with // odd sum exists or not int flag = -1; // Traverse the array for(int i = 0; i < n; ++i) { // If a pair exists with odd // sum, set flag = 1 if ((arr1[i] + arr2[i]) % 2 == 1) { flag = 1; break; } } // Print the answer and return System.out.print(flag); return; } // For all other cases, print -1 System.out.print(-1);}// Driver codepublic static void main(String[] args){ int arr1[] = { 11, 14, 20, 2 }; int arr2[] = { 5, 9, 6, 3 }; int N = arr1.length; // Function Call minimumSwaps(arr1, arr2, N);}}// This code is contributed by jithin |
Python3
# Python program for the above approach# Function to count the minimum swaps# of same-indexed elements from arrays# arr1 and arr2 required to make# the sum of both the arrays evendef minimumSwaps(arr1, arr2, n): # Store the sum of elements of # the array arr1 and arr2 respectively sumArr1 = 0; sumArr2 = 0; # Store the array sum of both the arrays for i in range(n): sumArr1 += arr1[i]; sumArr2 += arr2[i]; # If both sumArr1 and sumArr2 # are even, pr0 and return if (sumArr1 % 2 == 0 and sumArr2 % 2 == 0): print(0); return; # If both sumArr1 and sumArr2 # are odd and check for a pair # with sum odd sum if (sumArr1 % 2 != 0 and sumArr2 % 2 != 0): # Stores if a pair with # odd sum exists or not flag = -1; # Traverse the array for i in range(n): # If a pair exists with odd # sum, set flag = 1 if ((arr1[i] + arr2[i]) % 2 == 1): flag = 1; break; # Print the answer and return print(flag); return; # For all other cases, pr-1 print(-1);# Driver codeif __name__ == '__main__': arr1 = [11, 14, 20, 2]; arr2 = [5, 9, 6, 3]; N = len(arr1); # Function Call minimumSwaps(arr1, arr2, N); # This code is contributed by 29AjayKumar |
C#
// C# program to implement// the above approach using System;class GFG{ // Function to count the minimum swaps// of same-indexed elements from arrays// arr1[] and arr2[] required to make// the sum of both the arrays evenstatic void minimumSwaps(int[] arr1, int[] arr2, int n){ // Store the sum of elements of // the array arr1 and arr2 respectively int sumArr1 = 0, sumArr2 = 0; // Store the array sum of both the arrays for(int i = 0; i < n; ++i) { sumArr1 += arr1[i]; sumArr2 += arr2[i]; } // If both sumArr1 and sumArr2 // are even, print 0 and return if (sumArr1 % 2 == 0 && sumArr2 % 2 == 0) { Console.Write(0); return; } // If both sumArr1 and sumArr2 // are odd and check for a pair // with sum odd sum if (sumArr1 % 2 != 0 && sumArr2 % 2 != 0) { // Stores if a pair with // odd sum exists or not int flag = -1; // Traverse the array for(int i = 0; i < n; ++i) { // If a pair exists with odd // sum, set flag = 1 if ((arr1[i] + arr2[i]) % 2 == 1) { flag = 1; break; } } // Print the answer and return Console.Write(flag); return; } // For all other cases, print -1 Console.Write(-1);} // Driver codepublic static void Main(){ int[] arr1 = { 11, 14, 20, 2 }; int[] arr2 = { 5, 9, 6, 3 }; int N = arr1.Length; // Function Call minimumSwaps(arr1, arr2, N);}}// This code is contributed by susmitakundugoaldanga |
Javascript
<script>// Javascript program for the above approach// Function to count the minimum swaps// of same-indexed elements from arrays// arr1[] and arr2[] required to make// the sum of both the arrays evenfunction minimumSwaps(arr1, arr2, n){ // Store the sum of elements of // the array arr1 and arr2 respectively let sumArr1 = 0, sumArr2 = 0; // Store the array sum of both the arrays for(let i = 0; i < n; ++i) { sumArr1 += arr1[i]; sumArr2 += arr2[i]; } // If both sumArr1 and sumArr2 // are even, print 0 and return if (sumArr1 % 2 == 0 && sumArr2 % 2 == 0) { document.write(0); return; } // If both sumArr1 and sumArr2 // are odd and check for a pair // with sum odd sum if (sumArr1 % 2 != 0 && sumArr2 % 2 != 0) { // Stores if a pair with // odd sum exists or not let flag = -1; // Traverse the array for(let i = 0; i < n; ++i) { // If a pair exists with odd // sum, set flag = 1 if ((arr1[i] + arr2[i]) % 2 == 1) { flag = 1; break; } } // Print the answer and return document.write(flag); return; } // For all other cases, print -1 document.write(-1);}// Driver Codelet arr1 = [ 11, 14, 20, 2 ];let arr2 = [ 5, 9, 6, 3 ];let N = arr1.length;// Function CallminimumSwaps(arr1, arr2, N);// This code is contributed by splevel62</script> |
Output:
1
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
