Rearrange Odd and Even values in Alternate Fashion in Ascending Order
Given an array of integers (both odd and even), the task is to arrange them in such a way that odd and even values come in alternate fashion in non-decreasing order(ascending) respectively.
- If the smallest value is Even then we have to print Even-Odd pattern.
- If the smallest value is Odd then we have to print Odd-Even pattern.
Note: No. of odd elements must be equal to No. of even elements in the input array.
Examples:
Input: arr[] = {1, 3, 2, 5, 4, 7, 10}
Output: 1, 2, 3, 4, 5, 10, 7
Smallest value is 1(Odd) so output will be Odd-Even pattern.Input: arr[] = {9, 8, 13, 2, 19, 14}
Output: 2, 9, 8, 13, 14, 19
Smallest value is 2(Even) so output will be Even-Odd pattern.
Asked In: Microsoft Tech-Set-Go-2018
Algorithm:
- Sort the given array.
- Insert Even values in List-1 and Odd values in List-2.
- Now if the smallest value is even, then insert an even value from list 1 and odd value from list 2 to original array and so on.
- But if the smallest value is odd, then insert an odd value from list 2 and even value from list 1 to original array and so on.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; void AlternateRearrange( int arr[], int n) { // Sort the array sort(arr, arr + n); vector< int > v1; // to insert even values vector< int > v2; // to insert odd values for ( int i = 0; i < n; i++) if (arr[i] % 2 == 0) v1.push_back(arr[i]); else v2.push_back(arr[i]); int index = 0, i = 0, j = 0; bool flag = false ; // Set flag to true if first element is even if (arr[0] % 2 == 0) flag = true ; // Start rearranging array while (index < n) { // If first element is even if (flag == true ) { arr[index++] = v1[i++]; flag = !flag; } // Else, first element is Odd else { arr[index++] = v2[j++]; flag = !flag; } } // Print the rearranged array for (i = 0; i < n; i++) cout << arr[i] << " " ; } // Driver code int main() { int arr[] = { 9, 8, 13, 2, 19, 14 }; int n = sizeof (arr) / sizeof ( int ); AlternateRearrange(arr, n); return 0; } |
Java
// Java implementation of the above approach import java.util.* ; class GFG { static void AlternateRearrange( int arr[], int n) { // Sort the array // Collection.sort() sorts the // collection in ascending order Arrays.sort(arr) ; Vector v1 = new Vector(); // to insert even values Vector v2 = new Vector(); // to insert odd values for ( int i = 0 ; i < n; i++) if (arr[i] % 2 == 0 ) v1.add(arr[i]); else v2.add(arr[i]); int index = 0 , i = 0 , j = 0 ; boolean flag = false ; // Set flag to true if first element is even if (arr[ 0 ] % 2 == 0 ) flag = true ; // Start rearranging array while (index < n) { // If first element is even if (flag == true ) { arr[index] = ( int )v1.get(i); i += 1 ; index += 1 ; flag = !flag; } // Else, first element is Odd else { arr[index] = ( int )v2.get(j) ; j += 1 ; index += 1 ; flag = !flag; } } // Print the rearranged array for (i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } // Driver code public static void main(String []args) { int arr[] = { 9 , 8 , 13 , 2 , 19 , 14 }; int n = arr.length ; AlternateRearrange(arr, n); } } // This code is contributed by aishwarya.27 |
Python3
# Python3 implementation of the above approach def AlternateRearrange(arr, n): # Sort the array arr.sort() v1 = list () # to insert even values v2 = list () # to insert odd values for i in range (n): if (arr[i] % 2 = = 0 ): v1.append(arr[i]) else : v2.append(arr[i]) index = 0 i = 0 j = 0 flag = False # Set flag to true if first element is even if (arr[ 0 ] % 2 = = 0 ): flag = True # Start rearranging array while (index < n): # If first element is even if (flag = = True and i < len (v1)): arr[index] = v1[i] index + = 1 i + = 1 flag = ~flag # Else, first element is Odd elif j < len (v2): arr[index] = v2[j] index + = 1 j + = 1 flag = ~flag # Print the rearranged array for i in range (n): print (arr[i], end = " " ) # Driver code arr = [ 9 , 8 , 13 , 2 , 19 , 14 , 21 , 23 , 25 ] n = len (arr) AlternateRearrange(arr, n) # This code is contributed # by Mohit Kumar 29. |
C#
// C# implementation of the above approach using System; using System.Collections; class GFG { static void AlternateRearrange( int []arr, int n) { // Sort the array // Collection.sort() sorts the // collection in ascending order Array.Sort(arr) ; ArrayList v1 = new ArrayList(); // to insert even values ArrayList v2 = new ArrayList(); // to insert odd values for ( int j = 0; j < n; j++) if (arr[j] % 2 == 0) v1.Add(arr[j]); else v2.Add(arr[j]); int index = 0, i = 0, k = 0; bool flag = false ; // Set flag to true if first element is even if (arr[0] % 2 == 0) flag = true ; // Start rearranging array while (index < n) { // If first element is even if (flag == true ) { arr[index] = ( int )v1[i]; i += 1 ; index += 1 ; flag = !flag; } // Else, first element is Odd else { arr[index] = ( int )v2[k] ; k += 1 ; index += 1 ; flag = !flag; } } // Print the rearranged array for (i = 0; i < n; i++) Console.Write(arr[i] + " " ); } // Driver code static void Main() { int []arr = { 9, 8, 13, 2, 19, 14 }; int n = arr.Length ; AlternateRearrange(arr, n); } } // This code is contributed by mits |
PHP
<?php // PHP implementation of the above approach function AlternateRearrange( $arr , $n ) { // Sort the array sort( $arr ); $v1 = array (); // to insert even values $v2 = array (); // to insert odd values for ( $i = 0; $i < $n ; $i ++) if ( $arr [ $i ] % 2 == 0) array_push ( $v1 , $arr [ $i ]); else array_push ( $v2 , $arr [ $i ]); $index = 0; $i = 0; $j = 0; $flag = false; // Set flag to true if first element is even if ( $arr [0] % 2 == 0) $flag = true; // Start rearranging array while ( $index < $n ) { // If first element is even if ( $flag == true) { $arr [ $index ++] = $v1 [ $i ++]; $flag = ! $flag ; } // Else, first element is Odd else { $arr [ $index ++] = $v2 [ $j ++]; $flag = ! $flag ; } } // Print the rearranged array for ( $i = 0; $i < $n ; $i ++) echo $arr [ $i ], " " ; } // Driver code $arr = array ( 9, 8, 13, 2, 19, 14 ); $n = sizeof( $arr ); AlternateRearrange( $arr , $n ); // This code is contributed by Ryuga ?> |
Javascript
<script> // Javascript implementation of the above approach function AlternateRearrange(arr, n) { // Sort the array arr.sort((a,b)=>a-b); var v1 = []; // to insert even values var v2 = []; // to insert odd values for ( var i = 0; i < n; i++) if (arr[i] % 2 == 0) v1.push(arr[i]); else v2.push(arr[i]); var index = 0, i = 0, j = 0; var flag = false ; // Set flag to true if first element is even if (arr[0] % 2 == 0) flag = true ; // Start rearranging array while (index < n) { // If first element is even if (flag == true ) { arr[index++] = v1[i++]; flag = !flag; } // Else, first element is Odd else { arr[index++] = v2[j++]; flag = !flag; } } // Print the rearranged array for (i = 0; i < n; i++) document.write( arr[i] + " " ); } // Driver code var arr = [9, 8, 13, 2, 19, 14]; var n = arr.length; AlternateRearrange(arr, n); </script> |
2 9 8 13 14 19
Complexity Analysis:
- Time Complexity: O(N * logN)
- Auxiliary Space: O(N)
Efficient Approach :
We can use a pointer ‘wrong’ to point to the point to the wrong index of an element. Initially, we point wrong to -1, implying that wrong is not existing. If we come across another mistake, we swap both the mistakes and put wrong as -1, as both wrongs are swapped, and no wrongs exist until the traversed point.
Algorithm:
-> Sort the input vector
-> If the smallest number is even, every even index must have an even number and odd index must have an odd number. If this condition fails, initialize wrong as i if wrong = -1, or else swap wrong and i indices. Then put wrong = -1
-> If smallest number is odd, every even index must have an odd number and every odd index must have an even number. If this condition fails, initialize wrong as i if wrong = -1 or else swap wrong and i indices. Then put wrong = -1.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; void AlternateRearrange(vector< int >& arr, int n) { int wrong = -1; //pointer to point to wrong indices sort(arr.begin(), arr.end()); //sort the vector if (arr[0] % 2 == 0) { //smallest element is even for ( int i = 0; i < n; i++) { if ((i % 2 == 0 && arr[i] % 2 != 0) // if even number is not in even index || (i % 2 == 1 && arr[i] % 2 != 1)) { //or odd number is not in odd index if (wrong != -1) { //wrong index exists swap(arr[i], arr[wrong]); // swap previous wrong element and current wrong = -1; //wrong element. All elements are in correct position } else { //Wrong index is not existing wrong = i; //present index is wrong } } } } else { //smallest number is odd for ( int i = 0; i < n; i++) { if ((i % 2 == 0 && arr[i] % 2 != 1) // if even number is not in odd index || (i % 2 == 1 && arr[i] % 2 != 0)) { // or odd number is not in even index if (wrong != -1) { //wrong index exists swap(arr[i], arr[wrong]); // swap previous wrong element and current wrong = -1; //wrong element. All elements are in correct position } else { //Wrong index is not existing wrong = i; //present index is wrong } } } } } void printArray(vector< int >& arr, int n) { for ( int i = 0; i < n; i++) { cout << arr[i] << " " ; } cout << endl; } int main() { vector< int > arr = { 9, 8, 13, 2, 19, 14 }; int n = sizeof (arr) / sizeof (arr[0]); printArray(arr, n); AlternateRearrange(arr, n); printArray(arr, n); return 0; } |
Java
import java.util.*; public class Main { public static void AlternateRearrange(ArrayList<Integer> arr, int n) { int wrong = - 1 ; // pointer to point to wrong indices Collections.sort(arr); // sort the arraylist if (arr.get( 0 ) % 2 == 0 ) { // smallest element is even for ( int i = 0 ; i < n; i++) { if ((i % 2 == 0 && arr.get(i) % 2 != 0 ) // if even number is not // in even index || (i % 2 == 1 && arr.get(i) % 2 != 1 )) { // or odd number is // not in odd index if (wrong != - 1 ) { // wrong index exists Collections.swap( arr, i, wrong); // swap previous wrong // element and current wrong = - 1 ; // wrong element. All // elements are in // correct position } else { // Wrong index is not existing wrong = i; // present index is wrong } } } } else { // smallest number is odd for ( int i = 0 ; i < n; i++) { if ((i % 2 == 0 && arr.get(i) % 2 != 1 ) // if even number is not // in odd index || (i % 2 == 1 && arr.get(i) % 2 != 0 )) { // or odd number is // not in even index if (wrong != - 1 ) { // wrong index exists Collections.swap( arr, i, wrong); // swap previous wrong // element and current wrong = - 1 ; // wrong element. All // elements are in // correct position } else { // Wrong index is not existing wrong = i; // present index is wrong } } } } } public static void printArray(ArrayList<Integer> arr, int n) { for ( int i = 0 ; i < n; i++) { System.out.print(arr.get(i) + " " ); } System.out.println(); } public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<>( Arrays.asList( 9 , 8 , 13 , 2 , 19 , 14 )); int n = arr.size(); printArray(arr, n); AlternateRearrange(arr, n); printArray(arr, n); } } |
Python3
def AlternateRearrange(l): wrong = - 1 #pointer to point to wrong indices l.sort() #sort array if (l[ 0 ] % 2 = = 0 ): #smallest element is even for i in range ( len (l)): if (i % 2 = = 0 and l[i] % 2 ! = 0 ) or (i % 2 = = 1 and l[i] % 2 ! = 1 ): #if even number is not in even index or odd number is not in odd index if wrong ! = - 1 : #wrong index exists l[i], l[wrong] = l[wrong], l[i] #swap previous wrong element and current wrong element wrong = - 1 #All elements are in correct position else : #Wrong index is not existing wrong = i # present index is wrong else : #smallest element is odd for i in range ( len (l)): if (i % 2 = = 0 and l[i] % 2 ! = 1 ) or (i % 2 = = 1 and l[i] % 2 ! = 0 ): #if even number is not in odd index or odd number is not in even index if wrong ! = - 1 : #wrong index exists l[i], l[wrong] = l[wrong], l[i] #swap previous wrong element and current wrong element wrong = - 1 #All elements are in correct position else : #Wrong index is not existing wrong = i # present index is wrong def printArray(l): for i in range ( len (l)): print (l[i], end = " " ) print () l = [ 9 , 8 , 13 , 2 , 19 , 14 ] printArray(l) AlternateRearrange(l) printArray(l) |
C#
using System; public class Program { static void AlternateRearrange( int [] l) { int wrong = -1; // pointer to point to wrong indices Array.Sort(l); // sort array if (l[0] % 2 == 0) // smallest element is even { for ( int i = 0; i < l.Length; i++) { if ((i % 2 == 0 && l[i] % 2 != 0) || (i % 2 == 1 && l[i] % 2 != 1)) { // if even number is not in even index or odd number is not in odd index if (wrong != -1) // wrong index exists { int temp = l[wrong]; l[wrong] = l[i]; l[i] = temp; // swap previous wrong element and current wrong element wrong = -1; // all elements are in correct position } else // wrong index is not existing { wrong = i; // present index is wrong } } } } else // smallest element is odd { for ( int i = 0; i < l.Length; i++) { if ((i % 2 == 0 && l[i] % 2 != 1) || (i % 2 == 1 && l[i] % 2 != 0)) { // if even number is not in odd index or odd number is not in even index if (wrong != -1) // wrong index exists { int temp = l[wrong]; l[wrong] = l[i]; l[i] = temp; // swap previous wrong element and current wrong element wrong = -1; // all elements are in correct position } else // wrong index is not existing { wrong = i; // present index is wrong } } } } } static void PrintArray( int [] l) { for ( int i = 0; i < l.Length; i++) { Console.Write(l[i] + " " ); } Console.WriteLine(); } public static void Main() { int [] l = { 9, 8, 13, 2, 19, 14 }; PrintArray(l); AlternateRearrange(l); PrintArray(l); } } // This code is contributed by shivhack999 |
Javascript
// JavaScript program to rearrange an array such that even positioned are greater than odd. function AlternateRearrange(arr) { let n = arr.length; let wrong = -1; //pointer to point to wrong indices arr.sort((a, b) => a - b); //sort the array if (arr[0] % 2 == 0) { //smallest element is even for (let i = 0; i < n; i++) { if ((i % 2 == 0 && arr[i] % 2 != 0) // if even number is not in even index || (i % 2 == 1 && arr[i] % 2 != 1)) { //or odd number is not in odd index if (wrong != -1) { //wrong index exists [arr[i], arr[wrong]] = [arr[wrong], arr[i]]; // swap previous wrong element and current wrong = -1; //wrong element. All elements are in correct position } else { //Wrong index is not existing wrong = i; //present index is wrong } } } } else { //smallest number is odd for (let i = 0; i < n; i++) { if ((i % 2 == 0 && arr[i] % 2 != 1) // if even number is not in odd index || (i % 2 == 1 && arr[i] % 2 != 0)) { // or odd number is not in even index if (wrong != -1) { //wrong index exists [arr[i], arr[wrong]] = [arr[wrong], arr[i]]; // swap previous wrong element and current wrong = -1; //wrong element. All elements are in correct position } else { //Wrong index is not existing wrong = i; //present index is wrong } } } } return arr; } function printArray(arr) { console.log(arr.join( " " )); } let arr = [9, 8, 13, 2, 19, 14]; printArray(arr); arr = AlternateRearrange(arr); printArray(arr); |
Output:
2 9 8 13 14 19
Time Complexity Analysis:
- Time Complexity: O(N * logN), where N is the size of the array
- Auxiliary Space: O(1), where N is the size of the array