Given an array arr[] of integers of size n, the task is to check if we can sort the given array in non-decreasing order(i, e.arr[i] ≤ arr[i+1]) by using two types of operation by performing any numbers of time:
- You can choose any index from 1 to n-1(1-based indexing) and increase arr[i] and arr[i+1] by any positive numbers.
- You can choose any index from 1 to n-1 and decrease arr[i] and arr[i+1] by any positive numbers.
Note: Array elements can be negative at any point.
Examples:
Input: arr[] = {6, 4, 3, 5, 2 }
Output: YES
Explanation:
- Perform type-2 operation on index 1 and choose 4 and Now the array is- {2, 0, 3, 5, 2}
- Perform type-2 operation on index 3 and choose 4, Now the array becomes {2, 0, -1, 1, 2}
- Perform type-1 operation on index 2 and choose 2, Now the array becomes {2, 2, 1, 1, 2}
- Perform type-1 operation on index 3 and choose 1, Now the array becomes {2, 2, 2, 2, 2}
Now array {2, 2, 2, 2, 2}is sorted.
Input: arr[] = {3, 1, 5, 4 }
Output: NO
Explanation: If we make easily make arr[] = {3, 3, 3, 0} using type-1 operation, Now it is impossible to make the array sorted because we can’t perform an operation on the last index.
Approach: To solve the problem follow the below idea:
- If n is odd, Answer will be always Yes,
- Let’s prove: We will start from index 2 to n-1 and try to make arr[i] equal to arr[i-1], but we can not perform an operation on the last index. So, After performing the operation, our array will be like this {x, x….., x, y } y can be equal to x. But if y is not equal to x, we can make all array elements equal by pairing from the initial index and performing an operation on this like this {x, x, x, x, y}. After performing the operation, our array will be like this {x, x ….., x, x } which is sorted.
- If n is even, We will start iterating from index 2 to n-1 and try to make arr[i] equal to arr[i-1] by using increasing or decreasing operations. And in the last, check if
arr[n-1] ≤ arr[n], if this condition is satisfied, the Answer will be YES, else NO.
Below are the steps to implement the above idea:
- If n is odd, then print “YES” and return.
- If n is even, then start iterating from index 2 to n-1 and try to make all elements equal to the previous element.
- But we can’t perform an operation on the last index.
- If after iterating from index 2 to n-1, if arr[n-1] ≤ arr[n], so print the answer “YES”, else “NO”.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to check can we sort the// given operation using these two// types of operation any numbers of timebool makesorted(int* arr, int n){ // If n is odd, if (n % 2 != 0) { return true; } // Iterating from index 1 to n-2 for (int i = 1; i <= i - 2; i++) { // diff = difference between // arr[i-1] and arr[i] int diff = arr[i - 1] - arr[i]; // Adding diff to arr[i] // and arr[i+1] arr[i] += diff; // Making all elements equal // to first element arr[i + 1] += diff; } if (arr[n - 2] <= arr[n - 1]) { return true; } else { return false; }}// Driver codeint main(){ int arr[] = { 3, 1, 5, 4 }; int n = sizeof(arr) / sizeof(int); // Function call if (makesorted(arr, n)) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0;} |
Java
// Java code for the above approach:import java.util.Arrays;public class GFG { // Function to check if we can sort the given operation // using these two types of operations any number of // times static boolean makeSorted(int[] arr, int n) { // If n is odd if (n % 2 != 0) { return true; } // Iterating from index 1 to n-2 for (int i = 1; i <= i - 2; i++) { // diff = difference between arr[i-1] and arr[i] int diff = arr[i - 1] - arr[i]; // Adding diff to arr[i] and arr[i+1] arr[i] += diff; // Making all elements equal to the first // element arr[i + 1] += diff; } if (arr[n - 2] <= arr[n - 1]) { return true; } else { return false; } } // Driver code public static void main(String[] args) { int[] arr = { 3, 1, 5, 4 }; int n = arr.length; // Function call if (makeSorted(arr, n)) { System.out.println("YES"); } else { System.out.println("NO"); } }}// This code is contributed by shivamgupta0987654321 |
Python3
# Python3 code for the above approach:def makesorted(arr, n): # If n is odd, if n % 2 != 0: return True # Iterating from index 1 to n-2 for i in range(1, n - 1): # diff = difference between arr[i-1] and arr[i] diff = arr[i - 1] - arr[i] # Adding diff to arr[i] and arr[i+1] arr[i] += diff arr[i + 1] += diff # Checking if the last two elements are in non-decreasing order if arr[n - 2] <= arr[n - 1]: return True else: return False# Driver codearr = [3, 1, 5, 4]n = len(arr)# Function callif makesorted(arr, n): print("YES")else: print("NO")# This code is contributed by shivamgupta310570 |
C#
using System;class GFG { // Function to check if we can sort the given array // using the two types of operations any number of times static bool MakeSorted(int[] arr, int n) { // If n is odd if (n % 2 != 0) { return true; } // Iterating from index 1 to n-2 for (int i = 1; i <= n - 2; i++) { // diff = difference between arr[i-1] and arr[i] int diff = arr[i - 1] - arr[i]; // Adding diff to arr[i] and arr[i+1] arr[i] += diff; arr[i + 1] += diff; } if (arr[n - 2] <= arr[n - 1]) { return true; } else { return false; } } static void Main(string[] args) { int[] arr = { 3, 1, 5, 4 }; int n = arr.Length; // Function call if (MakeSorted(arr, n)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } }}// This code is contribute by shivamgupta0987654321 |
Javascript
// Function to check if we can sort the given array using the operations describedfunction makesorted(arr) { const n = arr.length; // If n is odd, we can sort using any number of operations if (n % 2 !== 0) { return true; } // Iterating from index 1 to n-2 for (let i = 1; i <= n - 2; i++) { // diff = difference between arr[i-1] and arr[i] const diff = arr[i - 1] - arr[i]; // Adding diff to arr[i] and arr[i+1] arr[i] += diff; // Making all elements equal to the first element arr[i + 1] += diff; } if (arr[n - 2] <= arr[n - 1]) { return true; } else { return false; }}// Driver codeconst arr = [3, 1, 5, 4];// Function callif (makesorted(arr)) { console.log("YES");} else { console.log("NO");}// This code is contributed by shivamgupta0987654321 |
Output
NO
Time Complexity: O(N)
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!
