Assuming that 'n' is passed along the function
Pseudocode 1: O(n*n)
construct_array (int *a, int n, int *output)
{
construct_linkedlist(1 ... n);
Node *current = list->head;
int i=0, j=0;
int tvar;
for(i=0;i<n;i++) {
if(a[i] == 0) {
output[j++] = list->head->data;
delete_head(llist);
} else {
for(tvar=a[i];tvar>1;tvar--)
current = current->next;
output[j++] = current->next->data;
remove_next(llist, current);
}
current = list->head;
}
}
Pseudocode 2: O(n*n)
construct_array(int *a, int n, int *output)
{
int i = 0, j = 0;
int op = 1;
while(op <= n) {
while(a[i++])
;
output[i] = op;
a[i] = -1;
for(j=0;j<i;j++)
a[j]--;
op++;
i = 0;
}
}
Algo 3: O(n*n)
construct a stack with no. from 1...n in it.
Read the input array pop that many elements and the stack top is the current
position in the output array. delete stack top after storing it in the
output array
push back the popped elements back
I am not sure whether an O(n) solution possible for this ...chk it out
anyway
On 5/4/07, Abhi <[EMAIL PROTECTED]> wrote:
>
>
> You are given an array of n numbers and each element is equal to the
> count of numbers less than that number in right hand side of the
> original and we have to find the original array;
> It is given that the n-numbers in the original array is from 1 to n.
>
> For ex. if the original array is 4,1,3,2
> Then we would we given the array 3,0,1,0
> 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
>
> Can any one suggest space and time efficient solution for this.
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
