Data Modelling & AI Data Structure & Algorithm

Rearrange sorted array such that all odd indices elements comes before all even indices element

23 June 2025

0

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 9

Input: 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 array
void 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 elements
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)
    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 Code
int 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 approach
import java.io.*;
 
class GFG 
{
 
// Function to print the array
static 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 elements
static 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 Code
public 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 array
def 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 elements
def 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 Code
if __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 approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to print the array
static 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 elements
static 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 Code
public 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 array
function 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 elements
function 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 Code
let 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 array
vector<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 usage
int 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 usage
arr = [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 usage
const 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!

Rearrange sorted array such that all odd indices elements comes before all even indices element

C++

Java

Python3

C#

Javascript

Approach: Two-Pointer Approach

C++

Java

Python3

Javascript

C#

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

This Garmin powerhouse outclasses every ‘Ultra’ watch, and calling it a must-buy feels like an understatement

Wear OS 6 lands on the Samsung’s Galaxy Watch 6 and Watch 6 Classic

T-Mobile will now start charging for a perk that used to be free

Spotify now lets you transfer playlists from other services

EDITOR PICKS

This Garmin powerhouse outclasses every ‘Ultra’ watch, and calling it a must-buy feels like an understatement

Wear OS 6 lands on the Samsung’s Galaxy Watch 6 and Watch 6 Classic

T-Mobile will now start charging for a perk that used to be free

POPULAR POSTS

This Garmin powerhouse outclasses every ‘Ultra’ watch, and calling it a must-buy feels like an understatement

Wear OS 6 lands on the Samsung’s Galaxy Watch 6 and Watch 6 Classic

T-Mobile will now start charging for a perk that used to be free

POPULAR CATEGORY

ABOUT US

FOLLOW US