In-Place Swapping

general
, ,
1

Hello friends I cam across this problem

If [a1,a2,a3…,an,b1,b2…bn] is given input change this to [a1,b1,a2,b2…an,bn] , solution should be in-place

I came with an idea ::
First swap elements in the middle pair

Next swap elements in the middle two pairs

Next swap elements in the middle three pairs

iterate n-1 steps.

Ex: with n = 4.

a1 a2 a3 a4 b1 b2 b3 b4

a1 a2 a3 b1 a4 b2 b3 b4

a1 a2 b1 a3 b2 a4 b3 b4

a1 b1 a2 b2 a3 b3 a4 b4

Can someone implement this in C++ . I know the problem asked is quite silly but I am not able to implement this using C++ . Somebody please help !!

OR

If anyone has a solution which takes O(n) time complexity and O(1) space complexity he/she is most welcome to add his code below in comments :slight_smile:

Space complexity of O(1) is the priority here .
Thanks in advance :slight_smile:

My Code ::
O(n^2 complexity)

Working :::

1st iteration :
abcedfgh
abecdfgh
aebcdfgh

2nd iteration :
aebcfdgh
aebfcdgh

3rd iteration :
aebfcgdh

2

Here is your code...

#include 
using namespace std;
void swap(int*,int*);
int main(){
	int n;
	cin>>n;
	int arr[2*n];
	for(int i=0;i<(2*n);i++){
		cin>>arr[i];
	}
	int k=n-1;
	int l=n;
	for(int i=0;i<n-1;i++){

	for(int j=k;j<=l;j+=2){
		swap(&arr[j],&arr[j+1]);
	}
	k--;
	l++;
}
for(int i=0;i<2*n;i++){
	cout<<arr[i]<<" ";
}



}

void swap(int *a, int *b){

int c;

c=*a;

*a=*b;

*b=c;

}
3

Time complexity O (N)

Space complexity O (1)

for (int i = 0; i <2*N;i++){

if (i%2==0)System.out.println (ar [i/2]);

else System.out.println(ar [N+i/2]);

}

4

I think we have to sort the array accordingly not output it.

1 Like
5

Don’t you think this is O(n^2) time complexity .

6

Rightly said we have to sort the array in the given format and also keeping it in-place . For me keeping it in-place is possible but the time complexity runs to O(n^2) . I want an improvement in time complexity . I have updated the post with my code .

7

Here is an approach which I guess is O(n) time complexity and O(1) complexity . Correct me if I am wrong .

Here is the proof :

I found following while testing it for input size upto 40

No for loop execution for input sizes:
2,4,6,12,14,20,30,38

for loop executes one time for input sizes:
8,10,18,24,26

for loop executes two times for input sizes:
28

for loop executes three times for input sizes:
16,34,40

for loop executes four times for input sizes:
22,36

for loop executes five times for input sizes:
32