Given an array A[] consisting of permutation of first N natural numbers, the task is to find the minimum number of operations required to modify A[] into an increasing array if an array element A[i] can be swapped with its next adjacent element A[i+1] at most twice. If it is not possible to modify the array into an increasing array, print -1.
Examples:
Input: A[] = [2,1,5,3,4]
Output: 3
Explanation:
Operation 1: Swap (Arr[2], Arr[3]). Therefore, A[] modifies to {2, 1, 3, 5, 4}.
Operation 2: Swap(arr[3], arr[4]). Therefore, A[] modifies to {2, 1, 3, 4, 5}.
Operation 3: Swap (arr[0], arr[1]). Therefore, A[] modifies to {1, 2, 3, 4, 5}.
Therefore, the sequence of operations are: {2, 1, 5, 3, 4} ? {2, 1, 3, 5, 4} ? {2, 1, 3, 4, 5} ? {1, 2, 3, 4, 5}Input: A[] = [2,5,1,3,4]
Output: -1
Approach: The idea is based on the observation that if an element A[i] is present at index i, then it must have moved from either index i – 1 or i – 2. This is because, to shift to A[i] from indices left of i – 2, the number of swaps would exceed 2. Therefore, traverse the array in reverse, and check if A[i] is present at its correct position or not. If found not to be, check A[i – 1] and A[i – 2] and update the count of operations accordingly. Follow the steps to solve the problem:
- Traverse the array, A[] over the indices [N – 1, 0] using a variable, say i.
- Store the correct index value in a variable, say X as i + 1.
- If the A[i] is currently not at its correct position, i.e. A[i] is not equal to X, then perform the following steps:
- If the value of A[i – 1] is equal to X, increment count by 1 and swap A[i] and A[i-1].
- Otherwise, if the value of A[i – 2] is equal to X, increment count by 2 and swap the pairs A[i – 2] and A[i – 1], then A[i – 2] and A[i].
- Otherwise, update the value of count to -1 and break out of the loop, since A[i] can not be swapped more than twice.
- After complete traversal of the array, print the value of count as the result.
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 minimum number of// operations required to obtain an// increasing array from given array A[]void minimumOperations(int A[], int n){ // Store the required result int cnt = 0; // Traverse the array A[] for (int i = n - 1; i >= 0; i--) { // If the current element is not // in its correct position if (A[i] != (i + 1)) { // Check if it is present at index i - 1 if (((i - 1) >= 0) && A[i - 1] == (i + 1)) { cnt++; swap(A[i], A[i - 1]); } // Check if it is present at index i-2 else if (((i - 2) >= 0) && A[i - 2] == (i + 1)) { cnt += 2; A[i - 2] = A[i - 1]; A[i - 1] = A[i]; A[i] = i + 1; } // Otherwise, print -1 (Since A[i] // can not be swapped more than twice) else { cout << -1; return; } } } // Print the result cout << cnt;}// Driver Codeint main(){ // Given array int A[] = {7, 3, 2, 1, 4 }; // Store the size of the array int n = sizeof(A) / sizeof(A[0]); minimumOperations(A, n); return 0;} |
Java
// Java program for the above approachimport java.util.*; import java.lang.*;class GFG{ // Function to count minimum number of// operations required to obtain an// increasing array from given array A[]static void minimumOperations(int A[], int n){ // Store the required result int cnt = 0; // Traverse the array A[] for(int i = n - 1; i >= 0; i--) { // If the current element is not // in its correct position if (A[i] != (i + 1)) { // Check if it is present at index i - 1 if (((i - 1) >= 0) && A[i - 1] == (i + 1)) { cnt++; int t = A[i]; A[i] = A[i-1]; A[i-1] = t; } // Check if it is present at index i-2 else if (((i - 2) >= 0) && A[i - 2] == (i + 1)) { cnt += 2; A[i - 2] = A[i - 1]; A[i - 1] = A[i]; A[i] = i + 1; } // Otherwise, print -1 (Since A[i] // can not be swapped more than twice) else { System.out.println(-1); return; } } } // Print the result System.out.println(cnt);}// Driver code public static void main(String[] args) { // Given array int A[] = { 7, 3, 2, 1, 4 }; // Store the size of the array int n = A.length; minimumOperations(A, n);} } // This code is contributed by souravghosh0416 |
Python3
# Python 3 program for the above approach# Function to count minimum number of# operations required to obtain an# increasing array from given array A[]def minimumOperations(A, n): # Store the required result cnt = 0 # Traverse the array A[] for i in range(n - 1, -1, -1): # If the current element is not # in its correct position if (A[i] != (i + 1)): # Check if it is present at index i - 1 if (((i - 1) >= 0) and A[i - 1] == (i + 1)): cnt += 1 A[i], A[i - 1] = A[i - 1], A[i] # Check if it is present at index i-2 elif (((i - 2) >= 0) and A[i - 2] == (i + 1)): cnt += 2 A[i - 2] = A[i - 1] A[i - 1] = A[i] A[i] = i + 1 # Otherwise, print -1 (Since A[i] # can not be swapped more than twice) else: print(-1) return # Print the result print(cnt)# Driver Codeif __name__ == "__main__": # Given array A = [7, 3, 2, 1, 4] # Store the size of the array n = len(A) minimumOperations(A, n) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;class GFG{ // Function to count minimum number of// operations required to obtain an// increasing array from given array A[]static void minimumOperations(int []A, int n){ // Store the required result int cnt = 0; // Traverse the array A[] for(int i = n - 1; i >= 0; i--) { // If the current element is not // in its correct position if (A[i] != (i + 1)) { // Check if it is present at index i - 1 if (((i - 1) >= 0) && A[i - 1] == (i + 1)) { cnt++; int t = A[i]; A[i] = A[i-1]; A[i-1] = t; } // Check if it is present at index i-2 else if (((i - 2) >= 0) && A[i - 2] == (i + 1)) { cnt += 2; A[i - 2] = A[i - 1]; A[i - 1] = A[i]; A[i] = i + 1; } // Otherwise, print -1 (Since A[i] // can not be swapped more than twice) else { Console.WriteLine(-1); return; } } } // Print the result Console.WriteLine(cnt);}// Driver code public static void Main() { // Given array int []A = { 7, 3, 2, 1, 4 }; // Store the size of the array int n = A.Length; minimumOperations(A, n);} } // This code is contributed by importantly. |
Javascript
<script>// Javascript program for the above approach // Function to count minimum number of // operations required to obtain an // increasing array from given array A function minimumOperations(A , n) { // Store the required result var cnt = 0; // Traverse the array A for (i = n - 1; i >= 0; i--) { // If the current element is not // in its correct position if (A[i] != (i + 1)) { // Check if it is present at index i - 1 if (((i - 1) >= 0) && A[i - 1] == (i + 1)) { cnt++; var t = A[i]; A[i] = A[i - 1]; A[i - 1] = t; } // Check if it is present at index i-2 else if (((i - 2) >= 0) && A[i - 2] == (i + 1)) { cnt += 2; A[i - 2] = A[i - 1]; A[i - 1] = A[i]; A[i] = i + 1; } // Otherwise, print -1 (Since A[i] // can not be swapped more than twice) else { document.write(-1); return; } } } // print the result document.write(cnt); } // Driver code // Given array var A = [ 7, 3, 2, 1, 4 ]; // Store the size of the array var n = A.length; minimumOperations(A, n);// This code contributed by Rajput-Ji</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!
