CareerCup

The idea is, for every index find the proper element which should seat at that position of the rearranged array, swap the two element, so element are rearranged from left side, now if the rearranged index is below than current iterator index that means the element is already swapped. So find the latest index where the element actually seat at that time which must be greater or equal to current index because left side of current index is already rearranged.

The algo does not used extra space and time complexity is O(n)

input a1,a2,a3,b1,b2,b3,c1,c2,c3
so element is 3 (series of a, series of b, and series of c)
and number is 3 (how many element in a series)

formula to find proper element for any index other that first or last element is
(number * index) % modulus (modulus = element * number -1)

rearrange(int a[], int element, int number)
{
  int swapIndex;

  //because 1st and last element of array is not swaping
  int modulo = (element * number) -1;
  for(index =1;index<modulo;index++)
  {
     //find the swap index which is equal or bigger than current index
     do{
              swapIndex = (number * index) % modulo;
      } while(swapIndex < index)
      
      if(swapIndex != index)
              swap(&a[index], &a[swapIndex]);
   }

}

#include<iostream.h>
#include<conio.h>
int a[]={1,2,3,4,5,6,7,8,9,10,11,12};
int n=sizeof(a)/sizeof(a[0]);
int count=0,row_size=n/3;
void swap(int i,int j)
{
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
void main()
{
	clrscr();
	int j=1,loc=j;
	for(int i=1;i<n-1;i++)
	{
		loc=(3*loc+loc/row_size)%n;
		if(j!=loc)
			swap(j,loc);
		else
		{
			j++;
			loc=j;
		}
	}
	for(int pos=0;pos<n;pos++)
		cout<<"  "<<a[pos];
	getch();
	}

By looking at problem it very much looks like a transpose of a matrix of order nX3.
Now just only difference here is that matrix is represented as single dimensional array rather than double dimensional array.
search in wikipedia for In-place_matrix_transposition and you will find nice article.

Below is the solution with O(N) time and O(1) space complexities.

#include <stdio.h>

/*
   Given the current index, count of groups and count of elements within each group,
   return the destination index where the current element should be placed to form
   the series [a1, b1, c1,...an, bn, cn] out of array 
   [a1, a2, a3, b1, b2, b3, c1, c2, c3 ... an, bn, cn]

   @idx - 
   @gc - count of groups
   @rc - count of elements within each group
*/
int get_idx(int idx, int gc, int rc)
{
    // gc = 3 (abc), rc = 4 (a1 a2 a3 a4)
    // 0  1  2  3  4  5  6  7  8  9  10 11
    // a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 
    // a1 b1 c1 a2 b2 c2 a3 b3 c3 a4 b4 c4 
    // 0  4  8  1  5  9  2  6  10 3  7  11
    
    int ogc, orc, didx = -1;
    
    ogc = idx / rc;
    orc = idx % rc;
    didx = orc * gc + ogc;
    
#if 0    
    printf("IDX: %-2d DIDX: %-2d OGC: %-2d ORC: %-2d\n", idx, didx, ogc, orc);
#endif

    return didx;
}

void test_get_idx(int gc, int rc)
{
    int tot = gc * rc;
    int didx;
    
    for (int i = 0; i < tot; i++){
        didx = get_idx(i, gc, rc);
        //printf("IDX: %-2d  DIDX: %-2d\n", i, didx);
    }
}

void swap(int arr[], int f, int s)
{
    int tmp;
    if(f == s)
        return;
    
    tmp = arr[f];
    arr[f] = arr[s];
    arr[s] = tmp;
}

/*
  Given an array of series like [a1,a2,...an, b1, b2,...bn, c1, c2, ...cn]
  do an in-place merge like [a1, b1, c1,... an, bn, cn].
  
  @cnt - array length. Is equal to (@gc * @rc)
  @gc - count of groups (a, b, c...)
  @rc - count of elements in each group (a1, b1, c1,...an)
*/
void merge_groups(int arr[], int cnt, int gc, int rc)
{
    int tc = cnt - 2;
    int i;
    int didx, cidx;
    int count = 1;
    
    for (i = 1; i < cnt; i++) {
        if (tc <= 0)
            break;

        cidx = i;
        didx = get_idx(cidx, gc, rc);

        while (i != didx){
            printf("ID: %-2d I: %-2d CIDX: %-2d DIDX: %-2d\n", count++, i, cidx, didx);
            swap(arr, i, didx);
            --tc;

            if (i == didx)
                break;
            cidx = didx;
            didx = get_idx(didx, gc, rc);
        }
        --tc; // Count the last too 
    }
}

void print_array(int arr[], int cnt, const char* cslabel)
{
    if (cslabel)
        printf("%s\n", cslabel);
        
    for (int i = 0; i < cnt; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(int argc, char *argv[])
{
    int arr[] = {1, 4, 7, 10, 2, 5, 8, 11, 3, 6, 9, 12};
    int cnt = sizeof(arr)/sizeof(arr[0]);
    int gc = 3;
    int rc = 4;
    
    if (gc * rc != cnt){
        printf("Count of groups (%d) and rank count(%d) do not match "
                "the array size (%d)", gc, rc, cnt);
        return 1;
    }
    
    print_array(arr, cnt, "Before:");
    merge_groups(arr, cnt, gc, rc);
    print_array(arr, cnt, "After:");
  
    return 0;
}

This question seems to has been double posted. Anyway, please see my complete solution at the link below:
w w w .careercup.com/question?id=13580673
Time complexity O(N), space O(1)
This implementation handles all the input values for Count of Groups(a b c ... x) and Count of Elements in the group (a1 a2 a3 a4 ... an).

int data[]={1,2,3,4,5,6,7,8,9,10,11,12};
int pattrenMix=4;
for(int i=0,j=0;i<data.length;i++){
System.out.print(data[j] + " ");
j=j+pattrenMix;
if(j>=data.length){
j=j-data.length+1;
}
}

Hi guys, i wrote this solution in java, i am pretty bad in find the code complexity, pleas someone validate the code.

I think code will fail for this input
a1 a2 a3 b1 b2 b3 c1 c2 c3.
If I understand code correctly ,
after i= 1 iteration array will be a1 b1 a3 a2 b2 b3 c1 c2 c3
=2 .............................. a1 b1 c1 a2 b2 b3 a3 c2 c3
now at i=3 iteration I will try to move a2 to its correct position...which is wrong as a2 is already at correct position.

pos=0;
for(i=0;i<3n;i++)
{
int a=pos%n;
int b=pos/n;

pos=0;
for(i=0;i<3n;i++)
{
int a=pos%n;
int b=pos/n;
newpos=a*3+b;
temp=A[newpos];
A[newpos]=A[pos];
pos=newpos;
}

#include <stdio.h>
#include <stdlib.h>
void in_order(int,int*);
int main(int argc, char *argv[])
{
int n,i,j;
int array[100];
printf("enter the size of the array\n");
scanf("%d",&n);
printf("enter the array elements\n");
for(i=0;i<n;i++)
scanf("%d",&array[i]);
in_order(n,array);


system("PAUSE");
return 0;
}
void in_order(int n1,int array1[])
{
int i,p,count,j,tmp;
p=(n1/3);
for(i=0;i<(n1-3);i++)
{
if(i%3==0)
{
i++;
p=p-1;
count=p;
}
for(j=count+i;j>i;j--)
{
tmp=array1[j];
array1[j]=array1[j-1];
array1[j-1]=tmp;
}
count=count*2;
}


for(i=0;i<n1;i++)
printf("%d ",array1[i]);

}

index = n/2;
1.Loop from i=1 to n/2
2.store current char in temp
3.shift array from i to index on right side
4.index++;i+=3;a[i]=temp
wll post the code in a while

Generalized for any number of groups.
If we observe, the pattern looks like following:
[ [0*n+1,0*n+2,0*n+3....0*n+n] [1*n+1,1*n+2,1*n+3....n+n] [2*n+1,2*n+2,2*n+3....2*n+n] .... [d*n+1, d*n+2,.... d*n+n] ]

And expected output is:
[ [0+1, n+1, 2n+2, ... d*n+1] [0+2, n+2, 2n+2,.... d*n+2]..... [0+n, n+n, 2n+n, ...d*n+n]

public static void main(String[] args) 
	{
	
		String[] array = {"a1","a2","a3","a4","b1","b2","b3","b4","c1","c2","c3","c4","d1","d2","d3","d4"};
				
		
		for(String item : array)
		{
			System.out.print(item + " ");
		}
		System.out.println();
		transpose(array,4); // n = 4
		for(String item : array)
		{
			System.out.print(item + " ");
		}
	}

	
	private static void transpose(Object[] a, int n) 
	{
			for(int i =0 ;i<a.length;i++)
			{
				
				if(i%n <= i/n)
				{
					continue;
				}
				
					int secondIndexToSwap = (i%n)* n + i/n;
					Object temp = a[i];
					a[i] = a[secondIndexToSwap];
					a[secondIndexToSwap]  = temp;
			
			}
	}

One solution ( though it’s a naive one) , but considering memory constraint , it would be ok

a1 a2 a3
b1 b2 b3
i.e. : a1 , a2 , a3 , b1, b2, b3

Steps to be follow :

Remove element column-wise starting from 1st element of next row , shift up the array and then put the element at the end of the array . Do it for all the elements in that column and then move to next column . Repeat this till the last element of the array ( i.e. c5)

e.g. :
a1,a2, a3,b1,b2,b3 – original
a1,a2,a3,b2,b3,b1 –step-1
a1,a3,b2,b3,b1,a2 –step-2
a1,a3,b3,b1,a2,b2–step-3
a1,b3,b1,a2,b2,a3 –step-4
a1, b1,a2,b2,a3,b3 – –step-5 - final result

i.e. :

a1,b1
a2,b2
a3,b3

i have implemented using O(3) memory in O(n) time...
plz suggest if better sol is possible..

main()
{
      int a[3];
      int ar[]={1,2,3,4,5,6,7,8,9,10,11,12};
      int n=sizeof ar/sizeof ar[0];
      int d=n/3;
      int ini=0,j,i;
      while(1)
      {
              j=0;
              for(i=ini;i<n;i+=d,j++)
              {
                                 a[j]=ar[i];
              }
              printf("%d %d %d ",a[0],a[1],a[2]);
              if(i-d==n-1)
              break;
              ini++;
      }
      getchar();
}

Here is a solution (algorithm) which uses additional memory complexity O(1) and run-time O(n).
----------------------------------------------------------------------------------------------------------------------------

Concept: For each element in the array find what would be its new position; then swap it with the element at the new position; continue this until there is nothing to swap.

input:
     ARR // an array with index left to right as 0,1,2,... 
     N   //considering ARR as an NxM matrix , N=number of rows
     M   //considering ARR as an NxM matrix , M=number of columns

Additional_Memory:
     ELE //holds an element from ARR or nothing
     INDX //holds the index of the element in ELE in original array ARR
     temp_element	//holds an element during swap

arrange( ARR, N, M)
	//move element at index 1 to Additional_memory & 
	//set array at index=1 as NULL
	Additional_Memory->ELE=ARR[1];
	Additional_Memory->INDX=1
	ARR[1]=NULL

	//Now the structure of the ARR is it has all elements as-is 
	//except the 2nd field from left (i.e. index=1) empty
	//and the Additional_Memory's ELE= [ARR's element at index=1]
	//and B=1 i.e. index of ELE

	while Additional_Memory is not empty //i.e. Additional_Memory->ELE != NULL
	do
		swap (Additional_Memory, ARR)
	done //end of while
end-of-arrange


//swaps array element at j with additional memory
swap (Additional_Memory, ARR) 
	//element in additional memory to be pushed to index j
	j=find_new_index_to_swap(Additional_Memory->INDX) 
	//swap additional-memory with element at index j in ARR
	temp_element=ARR[j]
	ARR[j]=Additional_Memory->ELE
	Additional_Memory->ELE=temp_element;
	Additional_Memory->INDX=j
end-of-swap

find_new_index_to_swap(indx)//definition
	j=(index % M)* N + (Indx / M )
	return j
end-of-find_new_index_to_swap

#include <stdio.h>
 
int findLocation(int i)
{
        return (i%4)*3 + (i/4);
}
 
void swap(int *a,int *b)
{
        int t=*a;
        *a=*b;
        *b=t;
}
 
void arrange(int *arr,int h)
{
        int i,j=1,loc=1;
        for(i=1;i<h-1;i++)
        {
                loc=findLocation(loc);
                if(loc!=j)
                        swap(&arr[loc],&arr[j]);
                else
                {
                        loc++;
                        j=loc;
                }
        }
}
 
int main()
{
        int arr[]={1,2,3,4,5,6,7,8,9,10,11,12},i;
 
        arrange(arr,12);
        for(i=0;i<12;i++)
                printf("%d ",arr[i]);
 
        return 0;
}

#include<iostream.h>
#include<conio.h>
int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
int n=sizeof(a)/sizeof(a[0]);
int count=0,row_size=n/3;
void swap(int i,int j)
{
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
void main()
{
	clrscr();
	int j=1,loc=j;
	for(int i=1;i<n-1;i++)
	{
		loc=(3*loc+loc/row_size)%n;
		if(j!=loc)
			swap(j,loc);
		else
		{
			j++;
			loc=j;
		}
	}
	for(int pos=0;pos<n;pos++)
		cout<<"  "<<a[pos];
	getch();
	}

move_element(unsigned a[], unsigned src, unsigned dst)
{
   temp = a[src];
   while(src != dest)
   {
     a[src] = a[src+1];
     src++;
   }  
   a[dest] = temp;
} 

merge_array(unsigned a[], unsigned length, unsigned sets)
{
    while(length > 0) {
       elements_in_set = length/sets;
       idx = sets;
       while(idx > 0)
       {
           move_element(a, elements_in_set * idx - 1, length-1);
           idx--;
           length--;
       } 
    } 
}

int * getMergedArray(int a[],int N ) {
/*N: size of the array */
if (N <= 6)
return NULL;

int* a1 = a;
int* a2 = a + (N / 3);
int* a3 = a + (2 * (N / 3 ));
int* result = (int*) malloc (N * sizeof(int));

int i = 0;
for (; i < N;)
{
if (!a1 || !a2 || !a3)
{
break;
}
result[i++] = *a1;
result[i++] = *a2;
result[i++] = *a3;
a1 = a1++;
a2 = a2++;
a3 = a3++;
}
if (i < N)
{
for (int j=i;j < N;j++)
{
result[j] = a[j];
}
}
if (result)
{
return result;
}
}

move_element(unsigned a[], unsigned src, unsigned dst)
{
   temp = a[src];
   while(src != dest)
   {
     a[src] = a[src+1];
     src++;
   }  
} 

merge_array(unsigned a[], unsigned length, unsigned sets)
{
    while(length > 0) {
       elements_in_set = length/sets;
       idx = sets;
       while(idx > 0)
       {
           move_element(a, elements_in_set * idx - 1, length-1);
           idx--;
           length--;
       } 
    } 
}