Regarding problem 2: If you really require o(n) rather than O(n), then you can't even look at all of the entries in the array.
If you know that one number appears multiple times and all of the other numbers are unique, then you do it in O(n) by looking for two adjacent numbers that are equal. That would have to be the one repeated value, and you can then count the number of occurrences in the array. If there are no adjacent equal values, then there cannot be n/2+1 equal values. I don't have an algorithm yet that will work in O(n) if there can be multiple repeated values and you have to find out if one of them is repeated n/2+1 times. Dave On Jan 25, 8:24 am, "kamalakannan .h" <[EMAIL PROTECTED]> wrote: > hai guys these questions were asked in anna university onsite programming > contest. > 1) find the second biggest number in a given array of size n. you have to > use n+logn number of searches or less > > 2) how will you find out if a number is repeated (n/2+1) times in an array > of size n? the complexity should be o(n). --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
