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
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)
Contact Us