CareerCup

void rearrange(int A[],int begin,int end)
{
if(begin+1==end)
return;
if(begin<end){
int mid=(begin+end)/2;
int r1=(begin+mid)/2;
int r2=(mid+1+end)/2;
int d=mid-begin;
int i,j;
if(d%2!=0){
j=mid+1;
for(i=r1+1;i<=mid;i++)
swap(&A[i],&A[j++]);
rearrange(A,begin,mid);
rearrange(A,mid+1,end);
}
else{
j=mid+1;
for(i=r1;i<=mid;i++)
swap(&A[i],&A[j++]);
swap(&A[mid],&A[mid+1]);
rearrange(A,begin,mid-1);
rearrange(A,mid+2,end);
}
}
}

here's my idea...

char[] organize( char[] string, int n )
    int distance = n;
    for ( int i = 0; distance > 0; i += 2, distance-- ) {
        char ci = string[i+distance+1];
        for ( int j = i + distance; j > i; j--) {
            string[j+1] = string[j];
        }
        string[i+1] = ci;
    }
}

rearrange( A[] , begin, end )
{
 if(begin<end){
        mid = (begin+end)/2
        r1 = (begin+mid)/2
        r2 = (mid+end)/2
        swap elements of r1-mid with mid-r2
        rearrange( A , begin, mid)
        rearrange( A , mid+1, end)

}
}

The element at the ith position in the final array will be at position
(i%2)*N + i/2 in the original array

Above logic can further extended for 'k' ;

k--> nos of groups of elements that compose given the given array

static void swap(int arr[],int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
static void rollBack(int arr[],int right,int left){
for(int i=right;i>left;i--)
arr[i] = arr[i-1];
}
static void reArrange(int array[]){
int index = array.length/2;
for(int i=1;i<array.length-1;i+=2){
int tmp = array[i];
swap(array,i,index);
rollBack(array, index++, i);
array[i+1] = tmp;
}
}