Array Rearrangement Without Another Array - Zoho Programming Round Question

Question:

You are given two integer arrays. The first one is a set of integers which you should rearrange and produce an output array based on the second array. The second array, we call it Order array, is an array which directs the rearrangement by specifying the required position of each element in given array. You should rearrange the elements just as specified by the order array without using any additional arrays. You should write a c program to rearrange the number array but without using another array. An example is as follows:

number array: 46   80  10   8    7    2   11   16  17  43
order array   :  5     2    0   6    8    7    1     3    4   9
output          :  2    10  46  11  17  16   80    8   7    43

Problem Explanation:

order[0]=5 means the current element at index 5 in the given number array should be at index 0 in the desired array. Similarly order[1]=2 means  the current element at index 2 in the given number array (10) should come at index 1 in the desired array.

Thus, the question is to write a c program to rearrange the given array without using another array to produce the desired array as specified by the order array.

This was one of the questions asked in a programming test conducted as a part of recruitment process of Zoho corporation, an IT firm. This is one of the tough c programming questions asked in second hands on coding round.

Before answering the question, you must know that it is possible to produce the desired output array without actually performing the rearrangement. It is not so difficult.The following code fragment can do it.

for(i=0;i<10;i++)

printf("%d  ",nums[order[i]]);

As emphasized in the question, the array should be rearranged, but your are not allowed to use any additional arrays.

Answer:

Actually, this can't be done without additional allocation of memory. But, to answer this question, we should avoid explicit use of additional arrays. So, we can make use of recursion. In fact, for each call of a recursive function, memory is allocated in stack for its local variables. We make use of recursion to exploit the stack. I would first write the program, then explain it.

#include<stdio.h>
int nums[]={ 46,80,10,8,7,2,11,16,17,43};
int order[]={5,2,0,6,8,7,1,3,4,9};
int i;
void rec(int index)
{
int num;
num=nums[order[index]];
if(index<9)
rec(index+1);
nums[index]=num;
}
void main()
{
printf("rearranging\n");
i=0;
rec(i);
printf("rearranged:\n");
for(i=0;i<10;i++)
printf("%d  ",nums[i]);
}

The parameter index in each recursion stores the index (position) and local variable num stores the desired number at that position. Thus value of parameter 'index' varies from 0 to 9 (here) and corresponding number at the index is also held in variable num. Thus, after the last call of recursive function, the whole array (index and the number at that index) get stored in stack. Only after this, the num is placed at its index.