Check if Array can be sorted by swapping adjacent elements having odd sum
Given an array arr[], the task is to check if the array can be sorted using the given operation any number of times. In one operation, you can swap any two adjacent elements if their sum is odd.
Examples:
Input: arr[] = [1, 6, 31, 14]
Output: Yes
Explanation: Swap 31 and 14 (31 + 14 = 45 which is odd). The array will be [1, 6, 14, 31] which is sorted.Input: arr[] = [4, 2]
Output: No
Explanation: Here no swap is possible. Hence the array can not be made sorted using the given operation.
Approach: To solve the problem follow the below idea:
Adjacent elements can only be swapped if they are of different parity. The given array can not be sorted if any element that is greater and of the same parity comes earlier in the array. So, If either the order of even elements or the order of odd elements is not non-decreasing, then it is impossible to sort the given array. We can made two separate arrays for storing even and odd elements and then can check either both of the arrays are in non-decreasing order or not separately.
Below are the steps for the above approach:
- Initialize two arrays/vectors say, even[] and odd[] that store even and odd elements respectively.
- Iterate the given array and check if arr[i] % 2 == 0, push the current element in the array even[], else push the current element in the array odd[].
- Check if both the arrays are separately in non-decreasing order, return true, else return false.
Below is the code for the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function for checking if it is // possible to sort the array bool check(vector< int >& arr, int n) { // Declare two arrays that store even // and odd elements seprately. vector< int > even; vector< int > odd; for ( int i = 0; i < arr.size(); i++) { // If the element is is even, push // it into even array if (arr[i] % 2 == 0) { even.push_back(arr[i]); } // Else push it in odd array else { odd.push_back(arr[i]); } } // Checking if the even array seprately // is sorted array or not, // if not return false. for ( int i = 1; i < even.size(); i++) { if (even[i - 1] > even[i]) { return false ; } } // Checking if the odd array seprately // is sorted array or not, // if not return false. for ( int i = 1; i < odd.size(); i++) { if (odd[i - 1] > odd[i]) { return false ; } } // If both the even and odd arrays // are seprately sorted, return true. return true ; } // Driver code int main() { vector< int > arr = { 1, 6, 31, 14 }; int n = arr.size(); // Function call bool flag = check(arr, n); if (flag == true ) cout << "Yes" << endl; else cout << "No" << endl; } |
Java
import java.util.*; public class Main { // Function for checking if it is // possible to sort the array public static boolean check(ArrayList<Integer> arr, int n) { // Declare two arrays that store even // and odd elements seprately. ArrayList<Integer> even = new ArrayList<Integer>(); ArrayList<Integer> odd = new ArrayList<Integer>(); for ( int i = 0 ; i < arr.size(); i++) { // If the element is is even, push // it into even array if (arr.get(i) % 2 == 0 ) { even.add(arr.get(i)); } // Else push it in odd array else { odd.add(arr.get(i)); } } // Checking if the even array seprately // is sorted array or not, // if not return false. for ( int i = 1 ; i < even.size(); i++) { if (even.get(i - 1 ) > even.get(i)) { return false ; } } // Checking if the odd array seprately // is sorted array or not, // if not return false. for ( int i = 1 ; i < odd.size(); i++) { if (odd.get(i - 1 ) > odd.get(i)) { return false ; } } // If both the even and odd arrays // are seprately sorted, return true. return true ; } // Driver code public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<Integer>(Arrays.asList( 1 , 6 , 31 , 14 )); int n = arr.size(); // Function call boolean flag = check(arr, n); if (flag == true ) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Prajwal Kandekar |
C#
// C# code for the above approach using System; using System.Collections.Generic; using System.Linq; public class GFG { // Function for checking if it is possible to sort the // array static bool Check(List< int > arr, int n) { // Declare two lists that store even and odd // elements separately. List< int > even = new List< int >(); List< int > odd = new List< int >(); for ( int i = 0; i < arr.Count; i++) { // If the element is even, add it to the even // list if (arr[i] % 2 == 0) { even.Add(arr[i]); } // Otherwise add it to the odd list else { odd.Add(arr[i]); } } // Check if the even list is sorted if not, return // false for ( int i = 1; i < even.Count; i++) { if (even[i - 1] > even[i]) { return false ; } } // Check if the odd list is sorted if not, return // false for ( int i = 1; i < odd.Count; i++) { if (odd[i - 1] > odd[i]) { return false ; } } // If both the even and odd lists are separately // sorted, return true. return true ; } static public void Main() { // Code List< int > arr = new List< int >{ 1, 6, 31, 14 }; int n = arr.Count; // Function call bool flag = Check(arr, n); if (flag == true ) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by lokesh. |
Python3
def check(arr): even = [] odd = [] # Separate even and odd numbers into different arrays for i in range ( len (arr)): if arr[i] % 2 = = 0 : even.append(arr[i]) else : odd.append(arr[i]) # Check if both even and odd arrays are sorted separately if sorted (even) = = even and sorted (odd) = = odd: return True else : return False # Driver code arr = [ 1 , 6 , 31 , 14 ] # Function call flag = check(arr) if flag: print ( "Yes" ) else : print ( "No" ) #code is contributed by Siddharth Aher |
Javascript
// Function for checking if it is // possible to sort the array function check(arr, n) { // Declare two arrays that store even // and odd elements seprately. let even = []; let odd = []; for (let i = 0; i < arr.length; i++) { // If the element is is even, push // it into even array if (arr[i] % 2 === 0) { even.push(arr[i]); } // Else push it in odd array else { odd.push(arr[i]); } } // Checking if the even array seprately // is sorted array or not, // if not return false. for (let i = 1; i < even.length; i++) { if (even[i - 1] > even[i]) { return false ; } } // Checking if the odd array seprately // is sorted array or not, // if not return false. for (let i = 1; i < odd.length; i++) { if (odd[i - 1] > odd[i]) { return false ; } } // If both the even and odd arrays // are seprately sorted, return true. return true ; } // Driver code let arr = [1, 6, 31, 14]; let n = arr.length; // Function call let flag = check(arr, n); if (flag === true ) console.log( "Yes" ); else console.log( "No" ); |
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us