Minimum swaps to make one Array lexicographically smaller than other
Consider two arrays arr1[] and arr2[] each of size N such that arr1[] contains all odd numbers between 1 to 2*N and arr2[] contains all even numbers between 1 to 2*N in shuffled order, the task is to make arr1[] lexicographically smaller than arr2[] by swapping the minimum number of adjacent elements.
Examples:
Input: arr1[] = {7, 5, 9, 1, 3} arr2[] = {2, 4, 6, 10, 8}
Output: 3
Explanation: After 1 swap operation arr1[] = {5, 7, 9, 1, 3}.
After two swap operations on arr2[] = {6, 2, 4, 10, 8}.
Now, arr1[] is lexicographically smaller than arr2[]. Total operations performed = 3.Input: arr1[] = {1, 3} arr2[]={2, 4}
Output: 0
Explanation: arr1[] is already lexicographically smaller than arr2[]. So output = 0.
Approach: To solve the problem follow the below idea:
arr1[] will be lexicographically smaller than arr2[], when the first element of the arr1[] will be smaller than the first element of arr2[].
Follow the steps to solve the problem:
- Create an array odd[] of size 2*N and store the position of all the odd numbers in which they appear in arr1[].
- Now for each odd number check the nearest greater number in arr2[].
- The no. of operations required to swap the elements to make it lexicographically smaller is given by
- The position of the odd element + position of the larger element in arr2[](even array) i.e. odd[element] + j
- Do it for each odd element and return the minimum of the operations required to achieve the task.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find minimum number // of operations to make arr1 // lexicographically smaller than arr2 int minimumOperations( int arr1[], int arr2[], int n) { int odd[2 * n]; for ( int i = 0; i < n; i++) { odd[arr1[i]] = i; } int cnt = 2 * n; int j = 0; for ( int i = 1; i < 2 * n; i += 2) { while (arr2[j] < i) j++; cnt = min(cnt, odd[i] + j); } // Return the number of operations return cnt; } // Driver code int main() { int arr1[] = { 7, 5, 9, 1, 3 }; int arr2[] = { 2, 4, 6, 10, 8 }; int N = sizeof (arr1) / sizeof (arr1[0]); // Function call cout << minimumOperations(arr1, arr2, N); return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to find minimum number of operations to make // arr1 lexicographically smaller that arr2 static int minimumOperations( int [] arr1, int [] arr2, int n) { int [] odd = new int [ 2 * n]; for ( int i = 0 ; i < n; i++) { odd[arr1[i]] = i; } int cnt = 2 * n; int j = 0 ; for ( int i = 1 ; i < 2 * n; i += 2 ) { while (arr2[j] < i) { j++; } cnt = Math.min(cnt, odd[i] + j); } // Return the number of operations return cnt; } public static void main(String[] args) { int [] arr1 = { 7 , 5 , 9 , 1 , 3 }; int [] arr2 = { 2 , 4 , 6 , 10 , 8 }; int N = arr1.length; // Function call System.out.print(minimumOperations(arr1, arr2, N)); } } // This code is contributed by lokeshmvs21. |
Python3
# Python code to implement the approach # Function to find minimum number # of operations to make arr1 # lexicographically smaller than arr2 def minimumOperations( arr1, arr2, n): odd = [ 0 ] * ( 2 * n) for i in range ( 0 ,n): odd[arr1[i]] = i cnt = 2 * n j = 0 for i in range ( 1 , 2 * n, + 2 ): while (arr2[j] < i): j + = 1 cnt = min (cnt, odd[i] + j) # Return the number of operations return cnt # Driver code arr1 = [ 7 , 5 , 9 , 1 , 3 ] arr2 = [ 2 , 4 , 6 , 10 , 8 ] N = len (arr1) # Function call print (minimumOperations(arr1, arr2, N)) # this code is contributed by ksam24000 |
C#
// C# code to implement the above approach using System; public class GFG { // Function to find minimum number of operations to make // arr1 lexicographically smaller that arr2 static int minimumOperations( int [] arr1, int [] arr2, int n) { int [] odd = new int [2 * n]; for ( int i = 0; i < n; i++) { odd[arr1[i]] = i; } int cnt = 2 * n; int j = 0; for ( int i = 1; i < 2 * n; i += 2) { while (arr2[j] < i) { j++; } cnt = Math.Min(cnt, odd[i] + j); } // Return the number of operations return cnt; } public static void Main( string [] args) { int [] arr1 = { 7, 5, 9, 1, 3 }; int [] arr2 = { 2, 4, 6, 10, 8 }; int N = arr1.Length; // Function call Console.WriteLine(minimumOperations(arr1, arr2, N)); } } // This code is contributed by AnkThon |
Javascript
<script> // JavaScript code to implement the approach // Function to find minimum number // of operations to make arr1 // lexicographically smaller than arr2 const minimumOperations = (arr1, arr2, n) => { let odd = new Array(2 * n).fill(0); for (let i = 0; i < n; i++) { odd[arr1[i]] = i; } let cnt = 2 * n; let j = 0; for (let i = 1; i < 2 * n; i += 2) { while (arr2[j] < i) j++; cnt = Math.min(cnt, odd[i] + j); } // Return the number of operations return cnt; } // Driver code let arr1 = [7, 5, 9, 1, 3]; let arr2 = [2, 4, 6, 10, 8]; let N = arr1.length; // Function call document.write(minimumOperations(arr1, arr2, N)); // This code is contributed by rakeshsahni </script> |
PHP
<?php // Function to find minimum number // of operations to make arr1 // lexicographically smaller than arr2 function minimumOperations( $arr1 , $arr2 , $n ) { $odd = array (); for ( $i = 0; $i < $n ; $i ++) { $odd [ $arr1 [ $i ]] = $i ; } $cnt = 2 * $n ; $j = 0; for ( $i = 1; $i < 2 * $n ; $i += 2) { while ( $arr2 [ $j ] < $i ) $j ++; $cnt = min( $cnt , $odd [ $i ] + $j ); } // Return the number of operations return $cnt ; } // Driver code $arr1 = array (7, 5, 9, 1, 3); $arr2 = array (2, 4, 6, 10, 8); $N = count ( $arr1 ); // Function call echo minimumOperations( $arr1 , $arr2 , $N ); // This code is contributed by Kanishka Gupta ?> |
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us