CareerCup

If you do merge sort, then you can check if the pivot point is at n/2 in the entire array, if yes, then return. I should be careful about n (odd or even).

Then use randomly merge sort, you should get O(log(n)) on average, however worst case is still O(n). You cannot do better.

Microsoft didn't ask you that. Stop trying to cheat on your randomized algorithms homework.

So, to be clear, at least n/2 of the elements are all the same element, and the other elements are all distinct from one another?

is that array s sorted of what kind of array it is? if it is a random array with repeated elements distributed randomly then i dont think there will be any algorithm to find the element rather than just traversing the array...

Correct me if am wrong!

Use majority number algorithm and check whether majority number count is actually n/2 or more

is that array s sorted of what kind of array it is? if it is a random array with repeated elements distributed randomly then i dont think there will be any algorithm to find the element rather than just traversing the array...
Correct me if am wrong! (c)

WTF, the guy told you, LAS VEGAS ALGORITHM. noone read the question?

fun(a,start,end){
if(a[start]==a[end]){ //found repeated
return a[start];
}else{
mid = start + (end-start)/2
fun(a,start,mid+1) //since n/2 elements are repeated so take n/2+1 window size
fun(a,mid-1,end)
}
}
//check the boundary conditions.