In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn]. We have to do it in O(1) extra space.

Transpose Algorithm 

Basically, we are converting rows into columns. E.g. a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should be changed to a1 b1 c1 a2 b2 c2 a3 b3 c3 a4 b4 c4.

a1 b1 c1 (i=1)

a2 b2 c2 (i=2)

a3 b3 c3 (i=3)

a4 b4 c4 (i= 4)

So we should write the array as a1 a2 a3 a4 b1 b2 b3 b4........, only this time, we are writiing column wise.

The program is recursive. The variable i is the number of groups

#include

#define SIZE 12 //multiple of 3

void arrange(int arr[], int n, int i)

{

if(i == 1)

{

arr[1] = arr[n];

arr[2] = arr[n <<1]

return;

}

int a = arr[i - 1];

int b = arr[n + i - 1];

int c = arr[2*n + i - 1];

arrange(arr, n, i - 1);

int x = 3 * (i - 1);

arr[x] = a;

arr[x + 1] = b;

arr[x + 2] = c;

}

int main()

{

int n = SIZE;

int a[SIZE], i;

printf("\nEnter %d numbers", SIZE);

for(i = 0; i <>

scanf("%d", a + i);

if(n != 0 && n % 3 == 0)arrange(a, n/3, n/3);

for(i = 0; i <n;i++)
printf(a[i]);

printf("\n");

}