Given an integer array, arr[] of size N and an integer X. The task is to sort the array in increasing order in a minimum number of moves by swapping any array element greater than X with X any number of times. If it is not possible print -1.
Examples:
Input: arr[] = {1, 3, 4, 6, 5}, X = 2
Output: 3
Explanation: Swap arr[1] = 3 with X = 2, arr[] becomes {1, 2, 4, 6, 5} and X = 3.
Swap arr[2] = 4 with X = 3, arr[] becomes {1, 2, 3, 6, 5} and X = 4.
Swap arr[3] = 6 with X = 4, arr[] becomes {1, 2, 3, 4, 5}.Input: arr[] = {7, 5}, X = 6
Output: -1
Explanation: It is not possible to sort the array using the given conditions.
Approach: The given problem can be solved by using the Greedy Approach. Follow the steps below to solve the problem:
- Initialize a variable ans as 0 to store the required result.
- Traverse the array, arr[] in the range [0, N-1] using the variable i
- If the value of arr[i]>arr[i+1], iterate in the range [0, i] using the variable j and swap arr[j] with X, if the value of arr[j]>X, while incrementing the value of ans by 1.
- Check if the array is sorted. If not, then update ans to -1.
- Print the value of ans 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 find the minimum number of // moves required to sort the array void minSwaps( int a[], int n, int x) { int c = 0; // Store the required number of moves int ans = 0; // Traverse the array, arr[] for ( int i = 0; i < n - 1; i++) { // If mismatch found if (a[i] > a[i + 1]) { // Start from first index to // maintain the increasing order // of array for ( int k = 0; k <= i; k++) { // If true, swap a[k] and x // and increment ans by 1 if (a[k] > x) { int tt = a[k]; a[k] = x; x = tt; ans++; } } } } // Check if now the array is sorted, // if not, set c=1 for ( int i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { c = 1; break ; } } // Print the result if (c == 1) { cout << "-1" ; } else { cout << ans; } } // Driver Code int main() { // Given Input int n = 5; int x = 2; int a[] = { 1, 3, 4, 6, 5 }; // Function Call minSwaps(a, n, x); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to find the minimum number of // moves required to sort the array static void minSwaps( int a[], int n, int x) { int c = 0 ; // Store the required number of moves int ans = 0 ; // Traverse the array, arr[] for ( int i = 0 ; i < n - 1 ; i++) { // If mismatch found if (a[i] > a[i + 1 ]) { // Start from first index to // maintain the increasing order // of array for ( int k = 0 ; k <= i; k++) { // If true, swap a[k] and x // and increment ans by 1 if (a[k] > x) { int tt = a[k]; a[k] = x; x = tt; ans++; } } } } // Check if now the array is sorted, // if not, set c=1 for ( int i = 0 ; i < n - 1 ; i++) { if (a[i] > a[i + 1 ]) { c = 1 ; break ; } } // Print the result if (c == 1 ) { System.out.println( "-1" ); } else { System.out.println(ans); } } // Driver Code public static void main (String[] args) { // Given Input int n = 5 ; int x = 2 ; int a[] = { 1 , 3 , 4 , 6 , 5 }; // Function Call minSwaps(a, n, x); } } // This code is contributed by Potta Lokesh |
Python3
# Python3 program for the above approach # Function to find the minimum number of # moves required to sort the array def minSwaps(a, n, x): c = 0 # Store the required number of moves ans = 0 # Traverse the array, arr[] for i in range (n - 1 ): # If mismatch found if (a[i] > a[i + 1 ]): # Start from first index to # maintain the increasing order # of array for k in range (i + 1 ): # If true, swap a[k] and x # and increment ans by 1 if (a[k] > x): tt = a[k] a[k] = x x = tt ans + = 1 # Check if now the array is sorted, # if not, set c=1 for i in range (n - 1 ): if (a[i] > a[i + 1 ]): c = 1 break # Print the result if (c = = 1 ): print ( "-1" ) else : print (ans) # Driver Code if __name__ = = '__main__' : # Given Input n = 5 x = 2 a = [ 1 , 3 , 4 , 6 , 5 ] # Function Call minSwaps(a, n, x) # This code is contributed by ipg2016107 |
C#
// C# program for the above approach using System; class GFG{ // Function to find the minimum number of // moves required to sort the array static void minSwaps( int [] a, int n, int x) { int c = 0; // Store the required number of moves int ans = 0; // Traverse the array, arr[] for ( int i = 0; i < n - 1; i++) { // If mismatch found if (a[i] > a[i + 1]) { // Start from first index to // maintain the increasing order // of array for ( int k = 0; k <= i; k++) { // If true, swap a[k] and x // and increment ans by 1 if (a[k] > x) { int tt = a[k]; a[k] = x; x = tt; ans++; } } } } // Check if now the array is sorted, // if not, set c=1 for ( int i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { c = 1; break ; } } // Print the result if (c == 1) { Console.Write( "-1" ); } else { Console.Write(ans); } } // Driver Code static public void Main() { // Given Input int n = 5; int x = 2; int [] a = { 1, 3, 4, 6, 5 }; // Function Call minSwaps(a, n, x); } } // This code is contributed by avijitmondal1998 |
Javascript
<script> // Javascript program for the above approach // Function to find the minimum number of // moves required to sort the array function minSwaps(a, n, x) { let c = 0; // Store the required number of moves let ans = 0; // Traverse the array, arr[] for (let i = 0; i < n - 1; i++) { // If mismatch found if (a[i] > a[i + 1]) { // Start from first index to // maintain the increasing order // of array for (let k = 0; k <= i; k++) { // If true, swap a[k] and x // and increment ans by 1 if (a[k] > x) { let tt = a[k]; a[k] = x; x = tt; ans++; } } } } // Check if now the array is sorted, // if not, set c=1 for (let i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { c = 1; break ; } } // Print the result if (c == 1) { document.write( "-1" ); } else { document.write(ans); } } // Driver Code // Given Input let n = 5; let x = 2; let a = [1, 3, 4, 6, 5]; // Function Call minSwaps(a, n, x); // This code is contributed by gfgking. </script> |
3
Time complexity: O(N2)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!