Given an array arr[] consisting of N integers, the task is to find the minimum number of swaps required to make the parity (i.e., even or odd) of all array elements same as their respective indices. If it is not possible to do so, then print “-1”.
Examples:
Input: arr[] = {3, 2, 7, 6}
Output: 2
Explanation:
Swap {arr[0], arr[1]} and {arr[2], arr[3]}. The array arr[] modifies to {2, 3, 6, 7}.
Now every odd and even element are at odd and even indices respectively.
Therefore, the minimum number of swaps required is 2.Input: arr[] = {7}
Output: -1
Approach: Follow the steps below to solve the problem:
- Initialize variables even and odd with 0, to store the count of even and odd numbers.
- Traverse the array arr[] using the variable i and perform the following:
- If the parity of arr[i] and i are the same, then continue.
- Check if i is even or not. If found to be true, then update even by incrementing the value by 1.
- Otherwise, update odd by incrementing the value by 1.
- After completing the above steps, if the value of even and odd are not equal, then print -1.
- Otherwise, print the value of even as the minimum number of swaps required.
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 number // of swaps required to make the parity // of array elements same as their indices void minimumSwaps( int arr[], int N) { // Stores count of even // and odd array elements int even = 0, odd = 0; // Traverse the array for ( int i = 0; i < N; i++) { // Check if indices and // array elements are not // of the same parity if (arr[i] % 2 != i % 2) { // If index is even if (i % 2 == 0) { // Update even even++; } else { // Update odd odd++; } } } // Condition for not possible if (even != odd) { cout << -1; } // Otherwise else { cout << even; } } // Driver Code int main() { int arr[] = { 3, 2, 7, 6 }; int N = sizeof (arr) / sizeof (arr[0]); minimumSwaps(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to count the minimum number // of swaps required to make the parity // of array elements same as their indices static void minimumSwaps( int arr[], int N) { // Stores count of even // and odd array elements int even = 0 , odd = 0 ; // Traverse the array for ( int i = 0 ; i < N; i++) { // Check if indices and // array elements are not // of the same parity if (arr[i] % 2 != i % 2 ) { // If index is even if (i % 2 == 0 ) { // Update even even++; } else { // Update odd odd++; } } } // Condition for not possible if (even != odd) { System.out.println(- 1 ); } // Otherwise else { System.out.println(even); } } // Driver Code public static void main(String[] args) { int arr[] = { 3 , 2 , 7 , 6 }; int N = arr.length; minimumSwaps(arr, N); } } // This code is contributed by Kingash |
Python3
# Python3 program for the above approach # Function to count the minimum number # of swaps required to make the parity # of array elements same as their indices def minimumSwaps(arr, N): # Stores count of even # and odd array elements even, odd = 0 , 0 # Traverse the array for i in range (N): # Check if indices and # array elements are not # of the same parity if (arr[i] % 2 ! = i % 2 ): # If index is even if (i % 2 = = 0 ): # Update even even + = 1 else : # Update odd odd + = 1 # Condition for not possible if (even ! = odd): print ( - 1 ) # Otherwise else : print (even) # Driver Code if __name__ = = '__main__' : arr = [ 3 , 2 , 7 , 6 ] N = len (arr) minimumSwaps(arr, N) # This code is contributed by mohit kumar 29. |
C#
// C# program to implement // the above approach using System; class GFG { // Function to count the minimum number // of swaps required to make the parity // of array elements same as their indices static void minimumSwaps( int [] arr, int N) { // Stores count of even // and odd array elements int even = 0, odd = 0; // Traverse the array for ( int i = 0; i < N; i++) { // Check if indices and // array elements are not // of the same parity if (arr[i] % 2 != i % 2) { // If index is even if (i % 2 == 0) { // Update even even++; } else { // Update odd odd++; } } } // Condition for not possible if (even != odd) { Console.WriteLine(-1); } // Otherwise else { Console.WriteLine(even); } } // Driver Code public static void Main() { int [] arr = { 3, 2, 7, 6 }; int N = arr.Length; minimumSwaps(arr, N); } } // This code is contributed by souravghosh0416. |
Javascript
<script> // Javascript program for the above approach // Function to count the minimum number // of swaps required to make the parity // of array elements same as their indices function minimumSwaps(arr, N) { // Stores count of even // and odd array elements let even = 0, odd = 0; // Traverse the array for (let i = 0; i < N; i++) { // Check if indices and // array elements are not // of the same parity if (arr[i] % 2 != i % 2) { // If index is even if (i % 2 == 0) { // Update even even++; } else { // Update odd odd++; } } } // Condition for not possible if (even != odd) { document.write(-1); } // Otherwise else { document.write(even); } } // Driver code let arr = [ 3, 2, 7, 6 ]; let N = arr.length; minimumSwaps(arr, N); // This code is contributed by target_2 </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!