Question: we have an array of 2n elements like "a1 a2...an b1 b2...bn". WAP to rearrange the array as "a1 b1 a2 b2...an bn"
time complexity is O(n) no extra array or memory can be taken...

I have an answer but could not meet the complexity requirement.

C code:

#include<stdio.h>
#define SWAP(a,b) a^=b^=a^=b

int string[100];
int m;

void Replace(int n,int start){
int i,j;
for(i=start,j=0;j<n;i++,j++)
SWAP(string[i],string[n+i]);
}
n=n-1;
if(n>0)
Replace(n,start+1);

main()
{
int i;
printf("Enter no of elements (max 100): ");
scanf("%d",&m);
if(m%2){
printf("odd nos\n");
else{
printf("Enter numbers: ");
for(i=0;i<m;i++)
scanf("%d",&string[i]);
for(i=0;i<m;i++)
printf("%d\t",string[i]);
printf("\n");

Replace(m/2-1,1);
for(i=0;i<m;i++)
printf("%d\t",string[i]);
printf("\n");
}
}

Output:

Enter no of elements (max 100): 12
Enter numbers:
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
1 7 2 8 3 9 4 10 5 11 6 12

Output with intermediate steps:
Enter no of elements (max 100): 12
Enter numbers:
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
1 7 8 9 10 11 2 3 4 5 6 12
1 7 2 3 4 5 8 9 10 11 6 12
1 7 2 8 9 10 3 4 5 11 6 12
1 7 2 8 3 4 9 10 5 11 6 12
1 7 2 8 3 9 4 10 5 11 6 12
1 7 2 8 3 9 4 10 5 11 6 12

If you can suggest a better solution, please revert.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.