Programming Test - Codility - Dominator

Question

I just experienced a codility problem that gave 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. Any solution for the same?

Answer 1

After I had Googled "computing dominant member of array", it was the first result which is mentioned below:-

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 you need to observe that if you find two different elements in the array, you can remove them both without changing the dominant element on the remainder. Also note that the code just keeps tossing out pairs of different elements, keeping track of the number of times it has seen the single remaining unpaired element.