Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement 
1.2.
Sample Examples
2.
Finding the middle index of the array
2.1.
Algorithm
2.2.
Implementation 
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
How to find the middle index of the array?
3.2.
Why is the time complexity of the program O(n^2)?
3.3.
Why is the space complexity O(1)?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

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];
}

 

Output

1 5 2 6 3 7 4 8

 

Time Complexity

The time complexity of this program is O(n2), 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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

How to find the middle index of the array?

You can find the middle index position “mi” using this formula, mi=(n-1)/2. Here n is the number of elements in the array.

Why is the time complexity of the program O(n^2)?

As we decrease the middle index by one each time. On the other hand, the inner loop runs for the middle index many times. We can think of it as two nested loops, with the outer loop running from i=0 to n and the inner loop running from i+1. As a result, the time complexity is polynomial.

Why is the space complexity O(1)?

Because the algorithm is an in-place algorithm, the space complexity is O(1). That is, all of the operations are replacing the initial array elements. And none of the new arrays are created.

Conclusion

This article extensively discussed the problem of creating a shuffled array of 2n integers as a1-b1-a2-b2-a3-b3-...bn without using extra space.
We hope this blog has helped you enhance your knowledge regarding array rearrangement problems. After reading about this topic, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered. To learn, see time complexity, and Complexity Analysis.

Recommended Problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! 

But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Split the array and add the first part to the end
Next article
Generate all Possible Sorted Arrays from Alternate Elements of Two Given Sorted Arrays
Live masterclass