Given an array A[], the task to find minimum swapping operations required to modify the given array A[] such that for every index in the array, parity(i) = parity(A[i]) where parity(x) = x % 2. If it’s impossible to obtain such an arrangement, then print -1.
Examples:
Input: A[] = { 2, 4, 3, 1, 5, 6 }
Output: 2
Explanation:
Swapping (4, 3) and (5, 6) modifies the array to [2, 3, 4, 1, 6, 5] such that the parity of i and A[i] is same for all indices.Input: A[] = {1, 2, 5, 7}
Output: -1
Explanation:
The given array cannot be rearranged as per required condition.
Approach:
To solve the problem mentioned above an optimal approach is to choose such an index where parity(i) and parity(A[i]) aren’t the same.
- Initialize two variables needodd and needeven to 0 which will store the parity of each element. Check the parity of index if it’s odd then increase needodd value by 1 otherwise increase needeven.
- If needodd and needeven aren’t same, then required arrangement is not possible.
- Otherwise, the final result is obtained by needodd variable, as it is the number of operations that are required. This is because, at any moment, we choose an odd element whose parity is not the same with parity of their index and similarly choose an even element and swap them.
Below is the implementation of the above approach:
C++
// C++ implementation to minimize // swaps required to rearrange // array such that parity of index and // corresponding element is same #include <bits/stdc++.h> using namespace std; // Function to return the // parity of number int parity(int x) { return x % 2; } // Function to return minimum // number of operations required int solve(int a[], int size) { // Initialize needodd and // needeven value by 0 int needeven = 0; int needodd = 0; for(int i = 0; i < size; i++) { if(parity(i) != parity(a[i])) { // Check if parity(i) is odd if(parity(i) % 2) { // increase needodd // as we need odd no // at that position. needodd++; } else { // increase needeven // as we need even // number at that position needeven++; } } } // If needeven and needodd are unequal if(needeven != needodd) return -1; else return needodd; } // Driver Code int main() { int a[] = { 2, 4, 3, 1, 5, 6}; int n = sizeof(a) / sizeof(a[0]); // Function call cout << solve(a, n) << endl; return 0; } // This code is contributed by venky07 |
Java
// Java implementation to minimize // swaps required to rearrange // array such that parity of index and // corresponding element is same import java.util.*;class GFG{ // Function to return the // parity of number static int parity(int x) { return x % 2; } // Function to return minimum // number of operations required static int solve(int a[], int size) { // Initialize needodd and // needeven value by 0 int needeven = 0; int needodd = 0; for(int i = 0; i < size; i++) { if(parity(i) != parity(a[i])) { // Check if parity(i) is odd if(parity(i) % 2 == 1) { // Increase needodd // as we need odd no // at that position. needodd++; } else { // Increase needeven // as we need even // number at that position needeven++; } } } // If needeven and needodd are unequal if(needeven != needodd) return -1; else return needodd; } // Driver Codepublic static void main (String[] args){ int a[] = { 2, 4, 3, 1, 5, 6}; int n = a.length; // Function call System.out.println(solve(a, n)); }}// This code is contributed by offbeat |
Python3
# Python3 implementation to minimize # swaps required to rearrange # array such that parity of index and # corresponding element is same # Function to return the # parity of number def parity(x): return x % 2# Function to return minimum # number of operations required def solve(a, size): # Initialize needodd and # needeven value by 0 needeven = 0 needodd = 0 for i in range(size): if parity(i)!= parity(a[i]): # Check if parity(i) is odd if parity(i) % 2: # increase needodd # as we need odd no # at that position. needodd+= 1 else: # increase needeven # as we need even # number at that position needeven+= 1 # If needeven and needodd are unequal if needodd != needeven: return -1 return needodd # Driver code if __name__ =="__main__": a = [2, 4, 3, 1, 5, 6] n = len(a) print(solve(a, n)) |
C#
// C# implementation to minimize // swaps required to rearrange // array such that parity of index and // corresponding element is same using System;class GFG{ // Function to return the // parity of number static int parity(int x) { return x % 2; } // Function to return minimum // number of operations required static int solve(int[] a, int size) { // Initialize needodd and // needeven value by 0 int needeven = 0; int needodd = 0; for(int i = 0; i < size; i++) { if(parity(i) != parity(a[i])) { // Check if parity(i) is odd if(parity(i) % 2 == 1) { // Increase needodd // as we need odd no // at that position. needodd++; } else { // Increase needeven // as we need even // number at that position needeven++; } } } // If needeven and needodd are unequal if(needeven != needodd) return -1; else return needodd; } // Driver Codepublic static void Main (){ int[] a = {2, 4, 3, 1, 5, 6}; int n = a.Length; // Function call Console.Write(solve(a, n)); }}// This code is contributed by Chitranayal |
Javascript
<script>// Javascript implementation to minimize // swaps required to rearrange array such// that parity of index and corresponding// element is same// Function to return the// parity of numberfunction parity(x){ return x % 2;}// Function to return minimum// number of operations requiredfunction solve(a, size){ // Initialize needodd and // needeven value by 0 let needeven = 0; let needodd = 0; for(let i = 0; i < size; i++) { if (parity(i) != parity(a[i])) { // Check if parity(i) is odd if (parity(i) % 2 == 1) { // Increase needodd // as we need odd no // at that position. needodd++; } else { // Increase needeven // as we need even // number at that position needeven++; } } } // If needeven and needodd are unequal if (needeven != needodd) return -1; else return needodd;}// Driver codelet a = [ 2, 4, 3, 1, 5, 6 ];let n = a.length;// Function calldocument.write(solve(a, n));// This code is contributed by rameshtravel07</script> |
Output:
2
Time Complexity: O(n), where n is the size of the given array
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!
