Given an array arr[] of N integers and an integer K, the task is to find the minimum number of operations required to sort the array in non-decreasing order such that in each operation any array element arr[i] can be swapped with K if the value of (arr[i] > K).
Examples:
Input: arr[] = {0, 2, 3, 5, 4}, K = 1
Output: 3
Explanation:
The given array can be sorted using the following steps:
- For i = 1, since arr[1] > K, swapping the values of arr[1] and K. Hence, the array becomes {0, 1, 3, 5, 4} and value of K = 2.
- For i = 2, since arr[2] > K, swapping the values of arr[2] and K. Hence, the array becomes {0, 1, 2, 5, 4} and value of K = 3.
- For i = 3, since arr[3] > K, swapping the values of arr[3] and K. Hence, the array becomes {0, 1, 2, 3, 4} and value of K = 5.
After the above operations, the given array has been sorted.
Input: arr[] = {1, 3, 5, 9, 7}, K = 10
Output: -1
Approach: The given problem can be solved using a Greedy Approach, the idea is to minimize the value of arr[i] at each step for all i in the range [0, N – 1] which is the most optimal choice for the further array to be sorted. Therefore, if the value of arr[i] > K, swapping the values of arr[i] and K is the most optimal choice. Follow the steps below to solve the given problem:
- Create a variable cnt, which stores the count of the operations performed. Initially cnt = 0.
- Traverse the array arr[] using a variable i in the range [0, N-1] in increasing order of i.
- For each index, if arr[i] > K, swap the value of K and arr[i] and increment the value of cnt by 1.
- After every operation, check whether the array arr[] is sorted or not using the approach discussed in this article. If the array arr[] is sorted, return the value of cnt as the required answer.
- If the array is not sorted after performing the above steps, the print -1.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number// of given operations in order to sort// the array arr[] in non-decreasing orderint minimumswaps(int arr[], int N, int K){ // If arr[] is already sorted, return 0 if (is_sorted(arr, arr + N)) { return 0; } // Stores the count of operations int cnt = 0; // Loop to iterate over the array for (int i = 0; i < N; i++) { // If arr[i] is greater than K, // minimize the value of arr[i] if (arr[i] > K) { swap(arr[i], K); // Increment the count by 1 cnt++; // Check if the array is sorted // after the last operation if (is_sorted(arr, arr + N)) { // Return answer return cnt; } } } // Not Possible to sort the array using // given operation, hence return -1 return -1;}// Driver Codeint main(){ int arr[] = { 0, 2, 3, 5, 4 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 1; cout << minimumswaps(arr, N, K); return 0;} |
Java
// Java program of the above approachimport java.io.*;class GFG{ static boolean is_sorted(int arr[], int N) { for (int i = 0; i < N - 1; i++) { if (arr[i] > arr[i + 1]) return false; } return true; } // Function to find the minimum number // of given operations in order to sort // the array arr[] in non-decreasing order static int minimumswaps(int arr[], int N, int K) { // If arr[] is already sorted, return 0 if (is_sorted(arr, N)) { return 0; } // Stores the count of operations int cnt = 0; // Loop to iterate over the array for (int i = 0; i < N; i++) { // If arr[i] is greater than K, // minimize the value of arr[i] if (arr[i] > K) { int temp = arr[i]; arr[i] = K; K = temp; // Increment the count by 1 cnt++; // Check if the array is sorted // after the last operation if (is_sorted(arr, N)) { // Return answer return cnt; } } } // Not Possible to sort the array using // given operation, hence return -1 return -1; } // Driver Code public static void main(String[] args) { int arr[] = { 0, 2, 3, 5, 4 }; int N = arr.length; int K = 1; System.out.println(minimumswaps(arr, N, K)); }}// This code is contributed by Dharanendra L V. |
Python3
# Python 3 program of the above approachdef is_sort(arr): for i in range(len(arr)-1): if arr[i]>arr[i+1]: return False return True # Function to find the minimum number# of given operations in order to sort# the array arr[] in non-decreasing orderdef minimumswaps(arr, N, K): # If arr[] is already sorted, return 0 if is_sort(arr): return 0 # Stores the count of operations cnt = 0 # Loop to iterate over the array for i in range(N): # If arr[i] is greater than K, # minimize the value of arr[i] if(arr[i] > K): temp = arr[i] arr[i] = K K = temp # Increment the count by 1 cnt += 1 # Check if the array is sorted # after the last operation if is_sort(arr): # Return answer return cnt # Not Possible to sort the array using # given operation, hence return -1 return -1# Driver Codeif __name__ == '__main__': arr = [0, 2, 3, 5, 4] N = len(arr) K = 1 print(minimumswaps(arr, N, K)) # This code is contributed by bgangwar59. |
C#
// C# program of the above approachusing System;class GFG { static bool is_sorted(int[] arr, int N) { for (int i = 0; i < N - 1; i++) { if (arr[i] > arr[i + 1]) return false; } return true; } // Function to find the minimum number // of given operations in order to sort // the array arr[] in non-decreasing order static int minimumswaps(int[] arr, int N, int K) { // If arr[] is already sorted, return 0 if (is_sorted(arr, N)) { return 0; } // Stores the count of operations int cnt = 0; // Loop to iterate over the array for (int i = 0; i < N; i++) { // If arr[i] is greater than K, // minimize the value of arr[i] if (arr[i] > K) { int temp = arr[i]; arr[i] = K; K = temp; // Increment the count by 1 cnt++; // Check if the array is sorted // after the last operation if (is_sorted(arr, N)) { // Return answer return cnt; } } } // Not Possible to sort the array using // given operation, hence return -1 return -1; } // Driver Code public static void Main(string[] args) { int[] arr = { 0, 2, 3, 5, 4 }; int N = arr.Length; int K = 1; Console.WriteLine(minimumswaps(arr, N, K)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach function is_sorted(arr, N) { for (let i = 0; i < N - 1; i++) { if (arr[i] > arr[i + 1]) return false; } return true; } // Function to find the minimum number // of given operations in order to sort // the array arr[] in non-decreasing order function minimumswaps(arr, N, K) { // If arr[] is already sorted, return 0 if (is_sorted(arr, N)) { return 0; } // Stores the count of operations let cnt = 0; // Loop to iterate over the array for (let i = 0; i < N; i++) { // If arr[i] is greater than K, // minimize the value of arr[i] if (arr[i] > K) { let temp = arr[i]; arr[i] = K; K = temp; // Increment the count by 1 cnt++; // Check if the array is sorted // after the last operation if (is_sorted(arr, N)) { // Return answer return cnt; } } } // Not Possible to sort the array using // given operation, hence return -1 return -1; } // Driver Code let arr = [0, 2, 3, 5, 4]; let N = arr.length; let K = 1; document.write(minimumswaps(arr, N, K)); // This code is contributed by Potta Lokesh </script> |
Output:
3
Time Complexity: O(N2)
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!
