Given an array arr[] of N integers, the task is to sort the array by replacing any element at index i (arr[i]) with arr[j] – arr[k] such that i < j < k.
Note: If no operation is needed print 0.
Examples:
Input: arr[] = {2, -2, -3, -1, 3}
Output:
3
3 4 5
2 4 5
1 4 5
Explanation: The number at 3rd position can be replaced by 4th and last position.
The array becomes {2, -2, -4, -1, 3}. So 31, 4, 5}
The number at 2nd position can be replaced by 4th and last position.
The array becomes {2, -4, -4, -1, 3}. So {2, 4, 5}
The number at 1st position can be replaced by 4th and last position.
The array becomes {-4, -4, -4, -1, 3}. So {1, 4, 5}
Array is sorted after 3 replacements, so 3 is printed at the beginning.Input: arr[] = {1, 2, -3, -5}
Output: -1
Explanation: The array can never be sorted by the following operations.
Approach: The approach is based on the fact that:
The last two elements can never get effected since the need is to select any 3 indices and i < j < k. So the replacement by the difference between the last two elements makes the array sorted if the last two are sorted.
Here are the cases that come:
Case-1: If arr[N-1] >= 0 and if the array is not sorted, the elements from the index i = [0, N – 3] can be replaced by arr[N – 2] – arr[N-1] since i < j < k and the difference arr[N – 2] – arr[N-1] will be less than a[N – 2].Case-2: If arr[N-1] < 0 it is not possible to make the array sorted by replacements.
If the last two elements arr[N – 1], arr[N-2] are sorted but a[N-1] < 0 then if some index i is chosen
arr[i] = arr[N-2] – (-a[N-1]) this becomes > a[N – 1] which violates the sorting property so NO.Case-3: If the last two elements are not sorted then sorting is not possible because we cant modify the last two elements any way.
Follow these steps to solve the above problem:
- Check if the last two elements are sorted or not since the operations can’t be made on them.
- If last element arr[N – 1] is greater than or equal to 0, replace the indices [0, N – 3] with arr[N – 2] – arr[N-1].
- If the last element is negative that can’t be sorted, if it was initially not sorted. So check if the array was sorted or not.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if the array// can be sorted with replacementsvoid is_possible(int arr[], int n){ // Check for the last two elements // if they are sorted or not // If they are not sorted print No if (arr[n - 2] > arr[n - 1]) { cout << "-1" << endl; return; } // If last element is greater than // or equal to 0 then elements index // [0, n-3] can be replaced by // a[n - 2] - a[n - 1] and it is // possible to sort the array if (arr[n - 1] >= 0) { cout << n - 2 << "\n"; for (int i = 0; i <= n - 3; i++) { cout << i + 1 << " " << n - 1 << " " << n << endl; } } // If arr[n-1] is negative, // it not possible except in case // the whole array is initially // negative sorted else { // Check if the array is sorted for (int i = 0; i < n - 2; i++) { if (arr[i] > arr[i + 1]) { cout << "-1" << endl; return; } } // If the array is initially sorted cout << "0" << endl; }}// Driver codeint main(){ int arr[] = { 2, -2, -3, -1, 3 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call is_possible(arr, N); return 0;} |
Java
// JAVA program for the above approachimport java.util.*;class GFG { // Function to check if the array // can be sorted with replacements public static void is_possible(int arr[], int n) { // Check for the last two elements // if they are sorted or not // If they are not sorted print No if (arr[n - 2] > arr[n - 1]) { System.out.println("-1"); return; } // If last element is greater than // or equal to 0 then elements index // [0, n-3] can be replaced by // a[n - 2] - a[n - 1] and it is // possible to sort the array if (arr[n - 1] >= 0) { System.out.println(n - 2); for (int i = 0; i <= n - 3; i++) { System.out.print(i + 1 + " "); System.out.print(n - 1 + " "); System.out.print(n); System.out.println(); } } // If arr[n-1] is negative, // it not possible except in case // the whole array is initially // negative sorted else { // Check if the array is sorted for (int i = 0; i < n - 2; i++) { if (arr[i] > arr[i + 1]) { System.out.println("-1"); return; } } // If the array is initially sorted System.out.println("0"); } } // Driver code public static void main(String[] args) { int arr[] = new int[] { 2, -2, -3, -1, 3 }; int N = arr.length; // Function call is_possible(arr, N); }}// This code is contributed by Taranpreet |
Python
# Python program for the above approach# Function to check if the array# can be sorted with replacementsdef is_possible(arr, n): # Check for the last two elements # if they are sorted or not # If they are not sorted print No if (arr[n - 2] > arr[n - 1]): print(-1) return # If last element is greater than # or equal to 0 then elements index # [0, n-3] can be replaced by # a[n - 2] - a[n - 1] and it is # possible to sort the array if (arr[n - 1] >= 0): print(n - 2) for i in range(0, n - 2): print(i + 1, n - 1, n) # If arr[n-1] is negative, # it not possible except in case # the whole array is initially # negative sorted else: # Check if the array is sorted for i in range(0, n - 2): if (arr[i] > arr[i + 1]): print("-1") return # If the array is initially sorted print("0")# Driver codeif __name__ == "__main__": arr = [ 2, -2, -3, -1, 3 ] N = len(arr) # Function call is_possible(arr, N) # This code is contributed by hrithikgarg03188. |
C#
// C# program for the above approachusing System;class GFG { // Function to check if the array // can be sorted with replacements static void is_possible(int[] arr, int n) { // Check for the last two elements // if they are sorted or not // If they are not sorted print No if (arr[n - 2] > arr[n - 1]) { Console.WriteLine("-1"); return; } // If last element is greater than // or equal to 0 then elements index // [0, n-3] can be replaced by // a[n - 2] - a[n - 1] and it is // possible to sort the array if (arr[n - 1] >= 0) { Console.WriteLine(n - 2); for (int i = 0; i <= n - 3; i++) { Console.WriteLine((i + 1) + " " + (n - 1) + " " + n); } } // If arr[n-1] is negative, // it not possible except in case // the whole array is initially // negative sorted else { // Check if the array is sorted for (int i = 0; i < n - 2; i++) { if (arr[i] > arr[i + 1]) { Console.WriteLine(-1); return; } } // If the array is initially sorted Console.WriteLine("0"); } } // Driver code public static void Main() { int[] arr = { 2, -2, -3, -1, 3 }; int N = arr.Length; // Function call is_possible(arr, N); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for the above approach // Function to check if the array // can be sorted with replacements const is_possible = (arr, n) => { // Check for the last two elements // if they are sorted or not // If they are not sorted print No if (arr[n - 2] > arr[n - 1]) { document.write("-1<br/>"); return; } // If last element is greater than // or equal to 0 then elements index // [0, n-3] can be replaced by // a[n - 2] - a[n - 1] and it is // possible to sort the array if (arr[n - 1] >= 0) { document.write(`${n - 2}<br/>`); for (let i = 0; i <= n - 3; i++) { document.write(`${i + 1} ${n - 1} ${n}<br/>`); } } // If arr[n-1] is negative, // it not possible except in case // the whole array is initially // negative sorted else { // Check if the array is sorted for (let i = 0; i < n - 2; i++) { if (arr[i] > arr[i + 1]) { document.write("-1<br/>"); return; } } // If the array is initially sorted document.write("0<br/>"); } } // Driver code let arr = [2, -2, -3, -1, 3]; let N = arr.length; // Function call is_possible(arr, N);// This code is contributed by rakeshsahni</script> |
3 1 4 5 2 4 5 3 4 5
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
