Shuffle 2n integers as a1-b1-a2-b2-a3-b3-...bn without using extra space

Introduction

Shuffling 2n integers as a1-b1-a2-b2-a3-b3-..bn without using extra space is an array rearrangement problem. This type of problem is asked in the interview to check the critical thinking aptitude of the candidate.

In this article, an optimal approach to solving this problem is discussed, along with its time complexity. So let’s get started!

Problem Statement 

We are given an array in the form of:

{a0, a1, a2….., an, b0, b1, b2, …..bn} 

Our task is to rearrange this array in the following form without using any extra space 

{a0, b0, a1, b1, a2, b2………..an, bn}

Sample Examples

Finding the middle index of the array

In order to find the shuffled array of 2n integers without using extra space, we will try to find the middle index of that array. Note that we can’t do this program for an array having an odd number or a null number of elements. We can only do this for an even number array. Now we will find the middle index. 

Since it is an even number array, there won’t be a single middle index but a set of 2, so we will take the latter and put it in the second position and shift the whole array afterward. Then we will find the next middle index without considering the shifted elements. We will do this operation until we get the shuffled integers array.
 

Algorithm

• Take the input of the array.
• When the array is empty, or the number of elements is odd, return.
• Now when the number of elements is even, find its middle index.
• While (middeindex>0)

set element = middleindex and swappedelement = middleindex

And

while (element-->0){

swap(swappedelement+1, swappedelement)

swappedelement++

 }

 middleindex--

•  End

Implementation 

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

// function to shuffle elements of the array
void shuffleelements(int array[], int n)
{

// for the case when array is empty or number of elements is odd
	if (array == NULL || n % 2 == 1)
	return;

// when number of element is even, start from the middle index
	int middleindex = (n - 1) / 2;

// each time, we will set two elements from the start to the valid position by swapping
	while (middleindex > 0)
	{
		int element = middleindex, swappedelement = middleindex;

		while (element-- > 0)
		{
			int temp = array[swappedelement + 1];
			array[swappedelement + 1] = array[swappedelement];
			array[swappedelement] = temp;
			swappedelement++;
		}

	middleindex--;
	}
}

// Main function of the program
int main()
{
	int array[] = {1, 2, 3 , 4, 5, 6, 7, 8};
	int n = sizeof(array) / sizeof(array[0]);
	shuffleelements(array, n);
	for (int i = 0; i < n; i++)
	cout << " " << array[i];
}

You can also try this code with Online C++ Compiler

Run Code

Output

1 5 2 6 3 7 4 8

Time Complexity

The time complexity of this program is O(n²), As we can see when we are decreasing the middle index by one. The inner loop runs again for that middle index. Same as two nested loops.

Space Complexity

The space complexity of this program will be O(1) as no extra auxiliary space was used.

Also see,  Rabin Karp Algorithm