Interview Q: How to Find the Most Popular Number in a Sorted Array

A number is popular if it is greater than or equal to N / 4 times (N is the length of the array). He wanted me to use a sorted array property and come up with a better solution than O (n) time complexity.

+3


source to share


1 answer


I would do it with a similar approach like binary search.

I would first find the values ​​of 8 numbers, which would be at 0/8, 1/8, 2/8 ... 8/8 of the array. The same numbers that you find when you binary search for something.

Since the same number must be n / 4 the size of the array or greater, it must reach at least two of these bounds per line. Like a number, 2/8 and 3/8 are the same.



Therefore, this identification of the number and the partial position is performed at a constant time.

Then you just keep finding where it starts and where it ends, which is a typical binary search.

Complexity: O(log n)

+2


source