Programming Test - Codility - Dominator [closed]

Question

I just had a codility problem give me a hard time and I'm still trying to figure out how the space and time complexity constraints could have been met.

The problem is as follows: A dominant member in the array is one that occupies over half the positions in the array, for example:

{3, 67, 23, 67, 67}

67 is a dominant member because it appears in the array in 3/5 (>50%) positions.

Now, you are expected to provide a method that takes in an array and returns an index of the dominant member if one exists and -1 if there is none.

Easy, right? Well, I could have solved the problem handily if it were not for the following constraints:

• Expected time complexity is O(n)
• Expected space complexity is O(1)

I can see how you could solve this for O(n) time with O(n) space complexities as well as O(n^2) time with O(1) space complexities, but not one that meets both O(n) time and O(1) space.

I would really appreciate seeing a solution to this problem. Don't worry, the deadline has passed a few hours ago (I only had 30 minutes), so I'm not trying to cheat. Thanks.

Answer 1

Googled "computing dominant member of array", it was the first result. See the algorithm described on page 3.

element x; int count ← 0; For(i = 0 to n − 1) {   if(count == 0) { x ← A[i]; count++; }   else if (A[i] == x) count++;   else count−−; } Check if x is dominant element by scanning array A 

Basically observe that if you find two different elements in the array, you can remove them both without changing the dominant element on the remainder. This code just keeps tossing out pairs of different elements, keeping track of the number of times it has seen the single remaining unpaired element.

Answer 2

Find the median with BFPRT, aka median of medians (O(N) time, O(1) space). Then scan through the array -- if one number dominates, the median will be equal to that number. Walk through the array and count the number of instances of that number. If it's over half the array, it's the dominator. Otherwise, there is no dominator.