Programming Test - Codility - Dominator

0 votes

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 in Java by Rahul
• 8,980 points

1 answer to this question.

0 votes

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.

answered Feb 11 by Soham
• 8,730 points

Related Questions In Java

0 votes
2 answers

How to test that an array contains a certain value?

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

answered Jul 17, 2018 in Java by Sushmita
• 6,900 points
0 votes
1 answer

Describe Heavy Weight Components Mean In Java Programming?

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

answered Nov 28, 2018 in Java by Frankie
• 9,830 points
0 votes
1 answer
0 votes
1 answer

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

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

answered Jan 7, 2019 in Java by Daisy
• 8,120 points
0 votes
1 answer

Creating a JUnit Test Suite Class

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

answered Jan 17, 2019 in Java by Frankie
• 9,830 points
0 votes
1 answer

What do you mean by Socket Programming?

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

answered Jul 14, 2019 in Java by Frankie
• 9,830 points
+5 votes
4 answers

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

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

answered Mar 27, 2018 in Java by DragonLord999
• 8,450 points

edited Nov 7, 2018 by Omkar 59,280 views
+1 vote
1 answer

How to handle drop downs using Selenium WebDriver in Java

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

answered Mar 27, 2018 in Selenium by nsv999
• 5,500 points
0 votes
1 answer

What are the differences between getText() and getAttribute() functions in Selenium WebDriver?

See, both are used to retrieve something ...READ MORE

answered Apr 5, 2018 in Selenium by nsv999
• 5,500 points
0 votes
1 answer

Selenium JARS(Java) missing from downloadable link

Nothing to worry about here. In the ...READ MORE

answered Apr 5, 2018 in Selenium by nsv999
• 5,500 points
Send OTP
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP