It's homework. For example If I have 10 elements in array then I have to find a element that appear at least 6 times in array, and it has to be done using divide and conquer and Moore's voting algorithm.

I have read many articles and found one solution this is the link http://www.geeksforgeeks.org/majority-element/ but here the times complexity is o(n logn) and I have to solve in o(n).

I take a idea from there and design my algorithm(Using Moore’s Voting Algorithm) as here. I divided it from middle and then again divide until it reach where I have 1 element. So during return I associate flag with the element and initial count which is going to be 1. and then compare two flags if same then add the count if different then minus the count.

I am able to solve some of the scenario like a={1,1,1,3,1,2,1,2,3,1,2,1} ,{1,1,1,3,1,2,1,2,3,7,2,1} but following are not giving me correct answer a={1,2,3,1,2,3}; count should be zero it is giving me count of 2.

Please let me know if somebody need code I can provide it ?

Again I have to use compulsorily divide and conquer and Moore's voting algorithm.

Thanks.

I have read many articles and found one solution this is the link http://www.geeksforgeeks.org/majority-element/ but here the times complexity is o(n logn) and I have to solve in o(n).

I take a idea from there and design my algorithm(Using Moore’s Voting Algorithm) as here. I divided it from middle and then again divide until it reach where I have 1 element. So during return I associate flag with the element and initial count which is going to be 1. and then compare two flags if same then add the count if different then minus the count.

I am able to solve some of the scenario like a={1,1,1,3,1,2,1,2,3,1,2,1} ,{1,1,1,3,1,2,1,2,3,7,2,1} but following are not giving me correct answer a={1,2,3,1,2,3}; count should be zero it is giving me count of 2.

Please let me know if somebody need code I can provide it ?

Again I have to use compulsorily divide and conquer and Moore's voting algorithm.

Thanks.

Last edited on

Using Moore's voting algorithm, first find the majority element in O(n).

Then on the second pass, just count the number of occurrences and if it is >= 6, return it.

Then on the second pass, just count the number of occurrences and if it is >= 6, return it.

Topic archived. No new replies allowed.