Check if Array can be sorted in non-decreasing order using given operations
Given an array arr[] of size N consisting of positive integers, the task is to check if the array can be sorted in non-decreasing order by performing the following operations:
- Select two adjacent elements.
- Swap the elements and invert their signs.
- All elements in the sorted array received at the end, must be positive.
Example:
Input: N = 4, arr[] = [4, 3, 2, 5]
Output: true
Explanation: In the given array, perform the following operations:
Swap arr[0] and arr[1] updated array: [-3, -4, 2, 5]
Swap arr[1] and arr[2] updated array: [-3, -2, 4, 5]
Swap arr[1] and arr[0] updated array: [2, 3, 4, 5]
The array is sorted in non-decreasing order and the elements are all positive.Input: N = 4, arr[] = [3, 3, 2, 2]
Output: true
Explanation: In the given array, perform the following operations :
Swap arr[0] and arr[2] updated array: [-2, 3, -3, 2]
Swap arr[1] and arr[3] updated array: [-2, -2, -3, -3]
Swap arr[1] and arr[0] updated array: [2, 2, -3, -3]
Swap arr[2] and arr[3] updated array: [2, 2, 3, 3]
The array is sorted in non-decreasing order and the elements are all positive.Input: N = 5, arr[] = [1, 2, 3, 5, 4]
Output: false
Explanation: There is no way to sort the array such that it follows all the mentioned conditions.
Approach: The problem can be solved using the Greedy approach based on the following observation:
Each number needs to move an even distance because they should all be positive at the end. And a positive number remains positive only after even number of inversion of signs.
So the difference of distance for all array elements between the given one and the sorted array must be even.
Follow the below steps to solve this problem:
- Initialize an empty map (say ctr[2][]) to keep the frequency of an array element in even position and odd position.
- Iterate over an array arr and increment the ctr[i % 1][arr[i]] by 1
- Sort the array arr[].
- Iterate over the array arr[] and decrement the ctr[i % 1][arr[i]] by 1.
- Iterate over the array arr[] and if ctr[1][a[i]] ≠ 0 or ctr[0][a[i]] ≠ 0 then return false.
- Otherwise, if the iteration is complete then return true.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to find if it is possible // to sort the array in non-decreasing order bool isItPossible( int n, vector< int >& a) { // Initializing a map 'ctr'. map< int , int > ctr[2]; // Iterating over an array and updating // the count for each occurrence for ( int i = 0; i < n; i++) { ctr[i % 2][a[i]]++; } // Sorting out the array sort(a.begin(), a.end()); // Updating count again according the // sorted array for ( int i = 0; i < n; i++) { ctr[i % 2][a[i]]--; } // Iterating over array again and if the // count is not zero then returning false for ( int i = 0; i < n; i++) { if (ctr[0][a[i]] != 0 || ctr[1][a[i]] != 0) { return false ; } } return true ; } // Driver code int main() { int N = 4; vector< int > arr = { 3, 3, 2, 2 }; // Function call cout << boolalpha << isItPossible(N, arr); return 0; } |
Java
// Java program for above approach import java.util.*; class GFG { // Function to find if it is possible // to sort the array in non-decreasing order public static boolean isItPossible( int n, int [] a) { // Initializing 2 maps 'ctr1' and 'ctr2' Map<Integer, Integer> ctr1 = new HashMap<Integer, Integer>(); Map<Integer, Integer> ctr2 = new HashMap<Integer, Integer>(); // Iterating over an array and updating // the count for each occurrence for ( int i = 0 ; i < n; i++) { if (i % 2 == 0 ) { if (ctr1.containsKey(a[i])) ctr1.put(a[i], ctr1.get(a[i]) + 1 ); else ctr1.put(a[i], 1 ); } else { if (ctr2.containsKey(a[i])) ctr2.put(a[i], ctr2.get(a[i]) + 1 ); else ctr2.put(a[i], 1 ); } } // Sorting out the array Arrays.sort(a); // Updating count again according the // sorted array for ( int i = 0 ; i < n; i++) { if (i % 2 == 0 ) { if (ctr1.containsKey(a[i])) ctr1.put(a[i], ctr1.get(a[i]) - 1 ); else ctr1.put(a[i], - 1 ); } else { if (ctr2.containsKey(a[i])) ctr2.put(a[i], ctr2.get(a[i]) - 1 ); else ctr2.put(a[i], - 1 ); } } // Iterating over array again and if the // count is not zero then returning false for ( int i = 0 ; i < n; i++) { if (ctr1.get(a[i]) != 0 || ctr2.get(a[i]) != 0 ) { return false ; } } return true ; } public static void main(String[] args) { int N = 4 ; int [] arr = { 3 , 3 , 2 , 2 }; // Function call System.out.println(isItPossible(N, arr)); } } // This code is contributed by phasing17 |
Python3
# Python3 code for the above approach # Function to find if it is possible # to sort the array in non-decreasing order def isItPossible(n, a): # Initializing a list of dicts 'ctr'. ctr = [ dict (), dict ()] # Iterating over an array and updating # the count for each occurrence for i in range (n): if a[i] in ctr[i % 2 ]: ctr[i % 2 ][a[i]] + = 1 else : ctr[i % 2 ][a[i]] = 1 # sorting the array a.sort() # updating count again according # to the sorted array for i in range (n): if a[i] in ctr[i % 2 ]: ctr[i % 2 ][a[i]] - = 1 # iterating over array again # and if the count is not zero # then returning false for i in range (n): if a[i] in ctr[ 0 ] and ctr[ 0 ][a[i]] ! = 0 or a[i] in ctr[ 1 ] and ctr[ 1 ][a[i]] ! = 0 : return False return True # Driver Code N = 4 arr = [ 3 , 3 , 2 , 2 ] # Function Call print (isItPossible(N, arr)) # This code is contributed by phasing17 |
C#
// C# program for above approach // Include namespace system using System; using System.Collections.Generic; using System.Linq; using System.Collections; public class GFG { // Function to find if it is possible // to sort the array in non-decreasing order public static bool isItPossible( int n, int [] a) { // Initializing 2 maps 'ctr1' and 'ctr2' var ctr1 = new Dictionary< int , int >(); var ctr2 = new Dictionary< int , int >(); // Iterating over an array and updating // the count for each occurrence for ( int i = 0; i < n; i++) { if (i % 2 == 0) { if (ctr1.ContainsKey(a[i])) { ctr1[a[i]] = ctr1[a[i]] + 1; } else { ctr1[a[i]] = 1; } } else { if (ctr2.ContainsKey(a[i])) { ctr2[a[i]] = ctr2[a[i]] + 1; } else { ctr2[a[i]] = 1; } } } // Sorting out the array Array.Sort(a); // Updating count again according the // sorted array for ( int i = 0; i < n; i++) { if (i % 2 == 0) { if (ctr1.ContainsKey(a[i])) { ctr1[a[i]] = ctr1[a[i]] - 1; } else { ctr1[a[i]] = -1; } } else { if (ctr2.ContainsKey(a[i])) { ctr2[a[i]] = ctr2[a[i]] - 1; } else { ctr2[a[i]] = -1; } } } // Iterating over array again and if the // count is not zero then returning false for ( int i = 0; i < n; i++) { if (ctr1[a[i]] != 0 || ctr2[a[i]] != 0) { return false ; } } return true ; } public static void Main(String[] args) { var N = 4; int [] arr = { 3, 3, 2, 2 }; // Function call Console.WriteLine(GFG.isItPossible(N, arr)); } } // This code is contributed by mukulsomukesh |
Javascript
<script> // JavaScript program for above approach // Function to find if it is possible // to sort the array in non-decreasing order const isItPossible = (n, a) => { // Initializing a map 'ctr'. let ctr = [{}, {}]; // Iterating over an array and updating // the count for each occurrence for (let i = 0; i < n; i++) { ctr[i % 2][a[i]] = a[i] in ctr[i % 2] ? ctr[i % 2][a[i]] + 1 : 1; } // Sorting out the array a.sort(); // Updating count again according the // sorted array for (let i = 0; i < n; i++) { if (a[i] in ctr[i % 2]) ctr[i % 2][a[i]]--; } // Iterating over array again and if the // count is not zero then returning false for (let i = 0; i < n; i++) { if (a[i] in ctr[0] && ctr[0][a[i]] != 0 || a[i] in ctr[1] && ctr[1][a[i]] != 0) { return false ; } } return true ; } // Driver code let N = 4; let arr = [3, 3, 2, 2]; s // Function call document.write(isItPossible(N, arr)); // This code is contributed by rakeshsahni </script> |
true
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)