Original array

/*
You are given an array of n numbers and each element is equal to the value of numbers less than that number in right hand side of the original array we have to find the original array
for ex. if the original array is 4,1,3,2
then we would we given the array 3,0,1,0
and we have to find the original array ,it is given that the numbers in the original array is from 1 to n.
ex no 2. original array 2,3,1,4
given array 1,1,0,0
ex no. 3 original array 5,2,1,3,4
given array 4,1,0,0,0
*/
Solution1:
main()
{
int *array;
int *value;
int *input;
int *orig;
unsigned int origIndex = 0;
unsigned int size = 0;
unsigned int sizeValue = 0;
unsigned int sizeArray = 0;
int i,j,k;
printf("Enter the size of input Array: ");
scanf(" %d",&size);
input = (int *)malloc(sizeof(int)*size);
array = (int *)malloc(sizeof(int)*size);
value = (int *)malloc(sizeof(int)*size);
orig = (int *)malloc(sizeof(int)*size);
for(i=0;i lessThan size;i++)
{
printf("Enter arr[%d]=",i);
scanf(" %d",&input[i]);
array[i] = i+1;
value[i] = i;
orig[i] = 0;
}
sizeValue = size;
for(i=0;i lessThan size;i++)
{
for(j=0;j lessThan sizeValue;j++)
{
if(input[i] == value[j])
{
orig[origIndex] = array[j];
origIndex++;
/*Shift the array and its value*/
for(k=j+1;k lessThan sizeValue;k++)
{
value[k] = (value[k] == 0)? 0: (value[k]-1);
}
for(k=j;k lessThan sizeValue-1;k++)
{
array[k] = array[k+1];
value[k] = value[k+1];
}
sizeValue--;
break;
}
}
}
printf("\n");
for(i=0;i lessThan size;i++)
printf("%2d",orig[i]);
printf("\n");
}



Solution2:
Let us assume that output has n elements.
We init an array say helperArray[i] = i; for i from 1 till n
Also have an outputArr[] which is init to 0.

Now take the input array inputArr[].
Step1. Check what is inputArr[i] let it be k.
Step2. Then we ask this qn what is the number which has exactly k lesser elements than itself. For this we check the helperArray[] and find the element from there. Let that element be helperArray[j]. Now strike of this element and do the above step again. But we dont take the striked off elements into considerations.

We take a simple example
let input 4 1 0 0 0
output 0 0 0 0 0
helper 1 2 3 4 5

Iteration1: k = 4 then output[0] = 5 as number which has 4 less numbers is 5
strike of 5 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 0 0 0 0
helper 1 2 3 4

Iteration2: k = 1 then output[1] = 2 as number which has 1 less numbers is 2
strike of 2 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 0 0 0
helper 1 3 4

Iteration3: k = 0 then output[2] = 1 as number which has 0 less numbers is 1
strike of 2 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 1 0 0
helper 3 4

Iteration4: k = 0 then output[3] = 3 as number which has 0 less numbers is 3
strike of 3 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 1 3 0
helper 3 4

Iteration5: k = 0 then output[4] = 4 as number which has 0 less numbers is 4
strike of 4 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 1 3 4
helper