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.