What exactly do you mean by a "step"? A comparison? A swap? An addition? A multiplication? Is more than one of these operations allowed in a single step?
I came across this puzzle before but in the version I saw it's number of comparisons that should be less than n+log(n). If it's the case of comparisons then my solution : let the array be A[0..n].Think of this as tournament.first 0 will play with 1,2 with 3,4 with 5 and so on.game between i and j will be won by i if A[i] > A[j].continue this process untill only one remains.The remaining one is largest and the second largest can only loose to the largest. so keep track of the list of numbers lost to a number.the maximum of the lost list of the final number gives the answer. Of course the above solution only works when numbers are distinct(atleast the number of maximums is 1.
5 comments:
What exactly do you mean by a "step"? A comparison? A swap? An addition? A multiplication? Is more than one of these operations allowed in a single step?
No. Only one of those operations is allowed in single step.
Actually, a small change : More than one of these are allowed in single step. But no two operations in a step must be same.
My Solution:
1. Construct a Max-heap in place. (N steps)
2. Delete the root. (log N steps)
3. Now, the root of the heap is the second-largest element.
I came across this puzzle before but in the version I saw it's number of comparisons that should be less than n+log(n).
If it's the case of comparisons then my solution :
let the array be A[0..n].Think of this as tournament.first 0 will play with 1,2 with 3,4 with 5 and so on.game between i and j will be won by i if A[i] > A[j].continue this process untill only one remains.The remaining one is largest and the second largest can only loose to the largest. so keep track of the list of numbers lost to a number.the maximum of the lost list of the final number gives the answer.
Of course the above solution only works when numbers are distinct(atleast the number of maximums is 1.
Post a Comment