Given a sorted array arr[] consisting of N positive integers, the task is to rearrange the array such that all the odd indices elements come before all the even indices elements.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Output: 2 4 6 8 1 3 5 7 9Input: arr[] = {0, 3, 7, 7, 10}
Output: 3 7 0 7 10
Approach: The given problem can be solved by modifying the given array by taking the value (maximum array element + 1) as the pivot(say) and then for the first half of the array add the value (arr[oddIndex]%pivot)*pivot at the odd indices oddIndex and for the second half of the array add the value (arr[evenIndex]%pivot)*pivot at the even indices evenIndex. After the above steps, divide each array element by the value of pivot. Below is the illustration for the same:
Consider the array arr[] = {3, 7}, then the value of pivot is 7 + 1 = 8.
For the first half:
Modify the array element arr[0] = 3 + (7%8)*8 = 3+ 56 = 59.For the second half:
Modify the array element arr[1] = 7 + (59%8)*8 = 7 + 24 = 31.
Dividing each array element by the pivot modifies the array to {7, 3} which is the required result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the arrayvoid printTheArray(int arr[], int N){ for (int i = 0; i < N; i++) cout << arr[i] << " ";}// Function to rearrange the array such// that odd indexed elements come before// even indexed elementsvoid rearrange(int arr[], int N){ //Reduces the size of array by one //because last element does not need //to be changed in case N = odd if (N & 1) N--; // Initialize the variables int odd_idx = 1, even_idx = 0; int i, max_elem = arr[N - 1] + 1; // Iterate over the range for (i = 0; i < N / 2; i++) { // Add the modified element at // the odd position arr[i] += (arr[odd_idx] % max_elem) * max_elem; odd_idx += 2; } // Iterate over the range for (; i < N; i++) { // Add the modified element at // the even position arr[i] += (arr[even_idx] % max_elem) * max_elem; even_idx += 2; } // Iterate over the range for (int i = 0; i < N; i++) { // Divide by the maximum element arr[i] = arr[i] / max_elem; }}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 16, 18, 19 }; int N = sizeof(arr) / sizeof(arr[0]); rearrange(arr, N); printTheArray(arr, N); return 0;}//This code is contributed by Akash Jha |
Java
// Java program for the above approachimport java.io.*;class GFG {// Function to print the arraystatic void printTheArray(int arr[], int N){ for (int i = 0; i < N; i++) System.out.print(arr[i] + " ");}// Function to rearrange the array such// that odd indexed elements come before// even indexed elementsstatic void rearrange(int arr[], int N){ // Reduces the size of array by one // because last element does not need // to be changed in case N = odd if ((N & 1) != 0) N--; // Initialize the variables int odd_idx = 1, even_idx = 0; int i, max_elem = arr[N - 1] + 1; // Iterate over the range for (i = 0; i < N / 2; i++) { // Add the modified element at // the odd position arr[i] += (arr[odd_idx] % max_elem) * max_elem; odd_idx += 2; } // Iterate over the range for (; i < N; i++) { // Add the modified element at // the even position arr[i] += (arr[even_idx] % max_elem) * max_elem; even_idx += 2; } // Iterate over the range for (i = 0; i < N; i++) { // Divide by the maximum element arr[i] = arr[i] / max_elem; }}// Driver Codepublic static void main (String[] args){ int arr[] = { 1, 2, 3, 4, 5, 16, 18, 19 }; int N = arr.length; rearrange(arr, N); printTheArray(arr, N);}}// This code is contributed by avijitmondal1998. |
Python3
# Python program for the above approach# Function to print the arraydef printArray(arr, n): for i in range(N): print(arr[i],end=" ") print("\n")# Function to rearrange the array such# that odd indexed elements come before# even indexed elementsdef rearrange(arr, N): #Reduces the size of array by one #because last element does not need #to be changed in case N = odd if (N & 1): N-=1 # Initialize the variables odd_idx = 1 even_idx = 0 max_elem = arr[N - 1] + 1 # Iterate over the range for i in range(N//2): # Add the modified element at # the odd position arr[i] += (arr[odd_idx] % max_elem) * max_elem odd_idx += 2 # Iterate over the range for i in range(N//2,N): # Add the modified element at # the even position arr[i] += (arr[even_idx] % max_elem) * max_elem even_idx += 2 # Iterate over the range for i in range(N): # Divide by the maximum element arr[i] = arr[i] // max_elem # Driver Codeif __name__=="__main__": arr = [ 1, 2, 3, 4, 5, 16, 18, 19 ] N = len(arr) rearrange(arr, N) printArray(arr, N);#This code is contributed by Akash Jha |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to print the arraystatic void printTheArray(int []arr, int N){ for (int i = 0; i < N; i++) Console.Write(arr[i]+" ");}// Function to rearrange the array such// that odd indexed elements come before// even indexed elementsstatic void rearrange(int []arr, int N){ // Reduces the size of array by one // because last element does not need // to be changed in case N = odd if ((N & 1) != 0) N--; // Initialize the variables int odd_idx = 1, even_idx = 0; int i, max_elem = arr[N - 1] + 1; // Iterate over the range for (i = 0; i < N / 2; i++) { // Add the modified element at // the odd position arr[i] += (arr[odd_idx] % max_elem) * max_elem; odd_idx += 2; } // Iterate over the range for (; i < N; i++) { // Add the modified element at // the even position arr[i] += (arr[even_idx] % max_elem) * max_elem; even_idx += 2; } // Iterate over the range for(i = 0; i < N; i++) { // Divide by the maximum element arr[i] = arr[i] / max_elem; }}// Driver Codepublic static void Main(){ int []arr = { 1, 2, 3, 4, 5, 16, 18, 19}; int N = arr.Length; rearrange(arr, N); printTheArray(arr, N);}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
// Function to print the arrayfunction printTheArray(arr, N) { for (let i = 0; i < N; i++) { console.log(arr[i] + " "); }}// Function to rearrange the array such// that odd indexed elements come before// even indexed elementsfunction rearrange(arr, N) { // Reduces the size of array by one // because last element does not need // to be changed in case N = odd if ((N & 1) !== 0) { N--; } // Initialize the variables let odd_idx = 1, even_idx = 0; let i, max_elem = arr[N - 1] + 1; // Iterate over the range for (i = 0; i < N / 2; i++) { // Add the modified element at // the odd position arr[i] += (arr[odd_idx] % max_elem) * max_elem; odd_idx += 2; } // Iterate over the range for (; i < N; i++) { // Add the modified element at // the even position arr[i] += (arr[even_idx] % max_elem) * max_elem; even_idx += 2; } // Iterate over the range for (i = 0; i < N; i++) { // Divide by the maximum element arr[i] = Math.floor(arr[i] / max_elem); }}// Driver Codelet arr = [1, 2, 3, 4, 5, 16, 18, 19];let N = arr.length;rearrange(arr, N);printTheArray(arr, N);//Thi code is Contributed by chinmaya121221 |
Output
2 4 16 19 1 3 5 18
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(1), as we are not using any extra space.
Approach: Two-Pointer Approach
- Initialize two pointers: one for odd-indexed elements (i = 1) and the other for even-indexed elements (j = 0).
- Traverse the input array from the beginning to the end, and for each element, do the following:
a. If the index is odd, append the element to the odd-indexed array at position i, and increment i by 2.
b. If the index is even, append the element to the even-indexed array at position j, and increment j by 2. - Merge the odd-indexed array and the even-indexed array to get the desired result.
C++
#include <iostream>#include <vector>using namespace std;// Function to rearrange an arrayvector<int> rearrange_array(vector<int> arr) { int n = arr.size(); vector<int> odd_arr(n / 2); vector<int> even_arr((n + 1) / 2); int i = 0; // pointer for odd-indexed elements int j = 0; // pointer for even-indexed elements for (int k = 0; k < n; k++) { if (k % 2 == 0) { // even index even_arr[j] = arr[k]; j++; } else { // odd index odd_arr[i] = arr[k]; i++; } } // Use insert instead of + odd_arr.insert(odd_arr.end(), even_arr.begin(), even_arr.end()); return odd_arr;}// Example usageint main() { vector<int> arr = {0,3,7,7,10}; vector<int> result = rearrange_array(arr); for (int x : result) { cout << x << " "; } cout << endl; return 0;} |
Java
import java.util.ArrayList;public class Main { // Function to rearrange an array static ArrayList<Integer> rearrangeArray(ArrayList<Integer> arr) { int n = arr.size(); ArrayList<Integer> oddArr = new ArrayList<Integer>(n / 2); ArrayList<Integer> evenArr = new ArrayList<Integer>((n + 1) / 2); int i = 0; // pointer for odd-indexed elements int j = 0; // pointer for even-indexed elements for (int k = 0; k < n; k++) { if (k % 2 == 0) { // even index evenArr.add(arr.get(k)); j++; } else { // odd index oddArr.add(arr.get(k)); i++; } } // Use addAll instead of + oddArr.addAll(evenArr); return oddArr; } // Example usage public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<Integer>(); arr.add(0); arr.add(3); arr.add(7); arr.add(7); arr.add(10); ArrayList<Integer> result = rearrangeArray(arr); for (int x : result) { System.out.print(x + " "); } System.out.println(); }} |
Python3
def rearrange_array(arr): n = len(arr) odd_arr = [0] * (n // 2) even_arr = [0] * ((n + 1) // 2) i = 0 # pointer for odd-indexed elements j = 0 # pointer for even-indexed elements for k in range(n): if k % 2 == 0: # even index even_arr[j] = arr[k] j += 1 else: # odd index odd_arr[i] = arr[k] i += 1 return odd_arr + even_arr# Example usagearr = [0,3,7,7,10]result = rearrange_array(arr)print(result) |
Javascript
function rearrangeArray(arr) { const n = arr.length; const oddArr = new Array(Math.floor(n/2)); const evenArr = new Array(Math.floor(n/2)); let i = 0; // pointer for odd-indexed elements let j = 0; // pointer for even-indexed elements for (let k = 0; k < n; k++) { if (k % 2 === 0) { // even index evenArr[j] = arr[k]; j++; } else { // odd index oddArr[i] = arr[k]; i++; } } return oddArr.concat(evenArr);}// Example usageconst arr = [0,3,7,7,10];const result = rearrangeArray(arr);console.log(result); |
C#
using System;using System.Collections.Generic;using System.Linq;class Program { static List<int> RearrangeArray(List<int> arr) { int n = arr.Count; List<int> oddArr = new List<int>(n / 2); List<int> evenArr = new List<int>((n + 1) / 2); int i = 0; // pointer for odd-indexed elements int j = 0; // pointer for even-indexed elements for (int k = 0; k < n; k++) { if (k % 2 == 0) { // even index evenArr.Add(arr[k]); j++; } else { // odd index oddArr.Add(arr[k]); i++; } } oddArr.AddRange(evenArr); return oddArr; } // Example usage static void Main(string[] args) { List<int> arr = new List<int>{0,3,7,7,10}; List<int> result = RearrangeArray(arr); foreach (int x in result) { Console.Write(x + " "); } Console.WriteLine(); }} |
Output
3 7 0 7 10
Time complexity: O(N), The time complexity of the rearrange_array function is O(n), where n is the size of the input array. This is because the function iterates through the entire array once to split it into two separate arrays based on odd and even indices, and then iterates through the two new arrays once more to combine them.
Auxiliary space: O(N), The space complexity of the function is O(n), where n is the size of the input array. This is because the function creates two new arrays to store the odd-indexed and even-indexed elements, respectively, and then combines them into a new array. The size of the two new arrays is proportional to the size of the input array, and the combined array is also the same size as the input array. Therefore, the space complexity is O(n).
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!
