Minimizing Swaps for Adjacent pair Sum Difference in Permutation
Given a permutation P of length n. The task is to find the minimum number of swaps required in the permutation such that the difference between the maximum value of (P[i] + P[i+1]) and the minimum value of (P[i] + P[i+1]), where 0 <= i <= n-2, is minimized.
Note: In other words, we want to rearrange the elements in the permutation to minimize the gap between the largest and smallest adjacent element sums.
Examples:
Input: n = 2, P = {1, 2}
Output: 0
Explanation: In the above permutations the gap between the largest and smallest adjacent element sums is already 0 and we cannot get lower value than 0.Input: n = 4, P = {1, 4, 3, 2}
Output: 1
Explanation: We can swap 1st and 2nd element to get { 4, 1, 3, 2 } where the largest sum of two adjacent element is 5 and smallest sum is 4 and the difference between them is 1. We cannot get a difference lower than 1.
Approach: This can be solved with the following idea:
Doing swapping between P and a vector created by seeing indexes even or odd. Check if values are equal or not, perform swaps and increment in number of swaps done.
Below are the steps involved:
- If size of array is 2, return 0.
- Create a 2 vecrors p1 and p2.
- Iterate over the array:
- If index is odd:
- p1.push_back(n + 1 – p1.back())
- p2.push_back(n + 1 – p2.back())
- If index is even:
- p1.push_back(n – p1.back())
- p2.push_back(n + 2 – p2.back())
- If index is odd:
- Check swapping function between p and p1, store the minimum swaps in ans.
- Reverse p1, call swap function, update the ans.
- Similar to do for p2 and p.
- Return ans.
Below is the implementation of the code:
C++
// C++ Implementation #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to swap int swaps(vector< int >& b, vector< int > a) { int n = a.size(); vector< int > pos(n + 1); // Iterate over the array for ( int i = 0; i < n; ++i) { pos[a[i]] = i; } int ans = 0; for ( int i = 0; i < n; ++i) { // If values are different if (a[i] != b[i]) { int j = pos[b[i]]; swap(a[i], a[j]); swap(pos[a[i]], pos[a[j]]); ++ans; } } // Return swaps return ans; } // Function to count minimum number of swaps // required to minimize the difference int minimumSwaps( int n, vector< int >& P) { // If array size is 2, return 0 if (n == 2) { return 0; } vector< int > p1; vector< int > p2; p1.push_back(n); p2.push_back(1); // Iterate over array for ( int i = 1; i < n; ++i) { // If index is odd if (i % 2 == 1) { p1.push_back(n + 1 - p1.back()); p2.push_back(n + 1 - p2.back()); } // If index is even else { p1.push_back(n - p1.back()); p2.push_back(n + 2 - p2.back()); } } // Perform swaps int ans = swaps(p1, P); reverse(p1.begin(), p1.end()); // Update the minimum swaps in ans ans = min(ans, swaps(p1, P)); ans = min(ans, swaps(p2, P)); reverse(p2.begin(), p2.end()); ans = min(ans, swaps(p2, P)); // Return ans return ans; } // Driver code int main() { int n = 2; vector< int > P = { 1, 2 }; // Function call cout << minimumSwaps(n, P); return 0; } |
Java
// Java Implementation import java.util.ArrayList; import java.util.Collections; import java.util.List; public class MinimumSwaps { public static int minimumSwaps( int n, List<Integer> P) { // If array size is 2, return 0 if (n == 2 ) { return 0 ; } List<Integer> p1 = new ArrayList<>(); List<Integer> p2 = new ArrayList<>(); p1.add(n); p2.add( 1 ); // Iterate over array for ( int i = 1 ; i < n; ++i) { // If index is odd if (i % 2 == 1 ) { p1.add(n + 1 - p1.get(p1.size() - 1 )); p2.add(n + 1 - p2.get(p2.size() - 1 )); } // If index is even else { p1.add(n - p1.get(p1.size() - 1 )); p2.add(n + 2 - p2.get(p2.size() - 1 )); } } // Perform swaps int ans = swaps(p1, P); Collections.reverse(p1); // Update the minimum swaps in ans ans = Math.min(ans, swaps(p1, P)); ans = Math.min(ans, swaps(p2, P)); Collections.reverse(p2); ans = Math.min(ans, swaps(p2, P)); // Return ans return ans; } public static int swaps(List<Integer> b, List<Integer> a) { int n = a.size(); List<Integer> pos = new ArrayList<>(Collections.nCopies(n + 1 , 0 )); // Iterate over the array for ( int i = 0 ; i < n; ++i) { pos.set(a.get(i), i); } int ans = 0 ; for ( int i = 0 ; i < n; ++i) { // If values are different if (!a.get(i).equals(b.get(i))) { int j = pos.get(b.get(i)); Collections.swap(a, i, j); Collections.swap(pos, a.get(i), a.get(j)); ++ans; } } // Return swaps return ans; } public static void main(String[] args) { int n = 2 ; List<Integer> P = new ArrayList<>(); P.add( 1 ); P.add( 2 ); // Function call System.out.println(minimumSwaps(n, P)); } } // This code is contributed by Tapesh(tapeshdua420) |
Python3
def swaps(b, a): n = len (a) pos = [ 0 ] * (n + 1 ) # Iterate over the array for i in range (n): pos[a[i]] = i ans = 0 for i in range (n): # If values are different if a[i] ! = b[i]: j = pos[b[i]] a[i], a[j] = a[j], a[i] pos[a[i]], pos[a[j]] = pos[a[j]], pos[a[i]] ans + = 1 # Return swaps return ans def minimum_swaps(n, P): # If array size is 2, return 0 if n = = 2 : return 0 p1 = [n] p2 = [ 1 ] # Iterate over array for i in range ( 1 , n): # If index is odd if i % 2 = = 1 : p1.append(n + 1 - p1[ - 1 ]) p2.append(n + 1 - p2[ - 1 ]) # If index is even else : p1.append(n - p1[ - 1 ]) p2.append(n + 2 - p2[ - 1 ]) # Perform swaps ans = swaps(p1, P) p1.reverse() # Update the minimum swaps in ans ans = min (ans, swaps(p1, P)) ans = min (ans, swaps(p2, P)) p2.reverse() ans = min (ans, swaps(p2, P)) # Return ans return ans # Driver code if __name__ = = "__main__" : n = 2 P = [ 1 , 2 ] # Function call print (minimum_swaps(n, P)) |
C#
using System; using System.Collections.Generic; public class GFG { public static int MinimumSwaps( int n, List< int > P) { // If array size is 2, return 0 if (n == 2) { return 0; } List< int > p1 = new List< int >(); List< int > p2 = new List< int >(); p1.Add(n); p2.Add(1); // Iterate over array for ( int i = 1; i < n; ++i) { // If index is odd if (i % 2 == 1) { p1.Add(n + 1 - p1[p1.Count - 1]); p2.Add(n + 1 - p2[p2.Count - 1]); } // If index is even else { p1.Add(n - p1[p1.Count - 1]); p2.Add(n + 2 - p2[p2.Count - 1]); } } // Perform swaps int ans = Swaps(p1, P); p1.Reverse(); // Update the minimum swaps in ans ans = Math.Min(ans, Swaps(p1, P)); ans = Math.Min(ans, Swaps(p2, P)); p2.Reverse(); ans = Math.Min(ans, Swaps(p2, P)); // Return ans return ans; } public static int Swaps(List< int > b, List< int > a) { int n = a.Count; List< int > pos = new List< int >( new int [n + 1]); // Iterate over the array for ( int i = 0; i < n; ++i) { pos[a[i]] = i; } int ans = 0; for ( int i = 0; i < n; ++i) { // If values are different if (a[i] != b[i]) { int j = pos[b[i]]; Swap(a, i, j); Swap(pos, a[i], a[j]); ++ans; } } // Return swaps return ans; } private static void Swap(List< int > list, int i, int j) { int temp = list[i]; list[i] = list[j]; list[j] = temp; } public static void Main( string [] args) { int n = 2; List< int > P = new List< int >{ 1, 2 }; // Function call Console.WriteLine(MinimumSwaps(n, P)); } } |
Javascript
// JS Implementation // Function to calculate swaps between two arrays function swaps(b, a) { const n = a.length; const pos = new Array(n + 1).fill(0); // Iterate over the array for (let i = 0; i < n; i++) { pos[a[i]] = i; } let ans = 0; for (let i = 0; i < n; i++) { // If values are different if (a[i] !== b[i]) { const j = pos[b[i]]; [a[i], a[j]] = [a[j], a[i]]; [pos[a[i]], pos[a[j]]] = [pos[a[j]], pos[a[i]]]; ans += 1; } } // Return swaps return ans; } // Function to calculate minimum swaps for a given array size and permutation function minimum_swaps(n, P) { // If array size is 2, return 0 if (n === 2) { return 0; } const p1 = [n]; const p2 = [1]; // Iterate over array for (let i = 1; i < n; i++) { // If index is odd if (i % 2 === 1) { p1.push(n + 1 - p1[p1.length - 1]); p2.push(n + 1 - p2[p2.length - 1]); } // If index is even else { p1.push(n - p1[p1.length - 1]); p2.push(n + 2 - p2[p2.length - 1]); } } // Perform swaps let ans = swaps(p1, P); p1.reverse(); // Update the minimum swaps in ans ans = Math.min(ans, swaps(p1, P)); ans = Math.min(ans, swaps(p2, P)); p2.reverse(); ans = Math.min(ans, swaps(p2, P)); // Return ans return ans; } // Driver code const n = 2; const P = [1, 2]; // Function call console.log(minimum_swaps(n, P)); // This code is contributed by Tapesh(tapeshdua420) |
0
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us