MR
BAN USERNothing.
Let's say i divide the horses in group like A,B,C,D,E and A[1]...E[1] are the first horses after Round 1.
In second round, we run A[1] to E[1] and let's say the result is 1st=A[1],2nd =B[1] 3rd=C[1].
So, A[1] is the fastest==>One horse found.
This is important, now we have to find the next two horses as we have to find 3 in total and we have already found 1.
These two can be A[2](second horse in A category after Round 1) & A[3](this means initial A group has all the fastest three horses)
There is a possibility that the second horse can also be B[1](second in Round 2) & third can be B[2](we dont need to consider B[3] here as that will mean we are considering B[1],B[2],B[3] where we have to find only the next two horses)So, we will take B[1] & B[2].
Because B[2] came second in Round 2, so the overall second must be anyone from B[1],B[2],A[2],A[3].We have to find one more place for overall third,so we will take C[1](third in Round 2)we do not need to consider C[2] here as we have already chosen top two & we just need the top third.
So, in the 3rd round(7th race) if we run A[2],A[3],B[1],B[2],C[1], the top two in this race along with A[1] wii give us the top three.
Vish,
Correct me if there was anything different in my understanding.
Saurabh,
How this algo will work if say i have array like 1,2,4,2,5,7,3,5,2(0 index)
So, the first element is already at its correct place, so how will it continue?
Should the algo be modified so that it will keep on swapping until it finds all the element(excluding the duplicates) are at their correct index position?
I think inorder traversal will work and you don't need a huge DS to store all the numbers.Just maintain two variable & compare currently read variable from the tree with the previously read var,if currently read is always greater than the prev read till we read the entire tree, it is BST, otherwise not.
- MR April 12, 2008