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?

Feb 11, 2022 in Java 689 views

## 1 answer to this question.

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.

• 9,700 points

## How to test that an array contains a certain value?

public static final String[] VALUES = new ...READ MORE

## Describe Heavy Weight Components Mean In Java Programming?

Heavy weight components like Abstract Window Toolkit ...READ MORE

## If The A Class Is Declared Without Any Access Modifiers, Where May The Class Be Accessed In Java Programming?

A class that is declared without any ...READ MORE

## How can I run test methods in specific order in JUnit4?

@FixMethodOrder(MethodSorters.NAME_ASCENDING) public class SampleTest { ...READ MORE

## Creating a JUnit Test Suite Class

To create a test suite we will use the ...READ MORE

## What do you mean by Socket Programming?

Socket programming is a way of connecting two ...READ MORE

## How to execute a python file with few arguments in java?

You can use Java Runtime.exec() to run python script, ...READ MORE

+1 vote

## How to handle drop downs using Selenium WebDriver in Java

First, find an XPath which will return ...READ MORE