Divide and conquer - Plural Array

6
votes

I want to design an algorithm that determines whether an array A is plural, and return that element.

An array is plural when there exists an element x in the array if more than half of the array is the same as x.

I am wondering if there is a more efficient divide and conquer algorithm that runs better than the current one i have now.

Assume you have the array

aaabbcac

i will recursively split the array up until i get subarrays of size 2, as follows.

aa ab bc ac

from here, i will compare each element in the SUBARRAY to see if they are equal: If EQUAL, return the element, Else, return false.

aa ab bc ac 
a  f   f  f

so now i have an array of the element A and 3 false.

i was thinking of combining them like so:

a  f  f  f
  a     f  <----- combining a and f will give a
     a    <----- returns a

But, if we look at the array, we have 4 A's, which does not fulfill the criteria of a plural array. It should return false, should the array not be a plural array.

I believe my algorithm will run in O(n lgn), should it be a correct algorithm, which unfortunately is not.

Can anyone point me in the right direction for this?

3
algorithm
Does is have to be a divide & conquer approach ? - gusbro
Yes I am looking for a divide and conquer algorithm. - ali
Is this homework? You were very close.... - Neil G
Yeah its homework. But I'm pretty stumped on how to continue from here. Any tips? - ali
Recent question about an O(n) algorithm for finding the element if the element exists. - aaz

3 Answers

1
votes

This is a problem of counting number of occurrences of x. Split the array into sub arrays and send the x along with sub arrays. Return count, sum counts and check if it's greater then the size of the array.

1
votes

Since it's homework, here's clues - you should be able to prove these easily and finish the question.

  • A single element array trivially has a plural element
  • An array has at most one plural element, suppose it exists and call it x.
  • If you partition the array into two halves, x will be a plural element of at least one of the halves.
1
votes

You can also sort array by some sorting algorithm (such as quicksort), after that loop until (N+1)/2 element by checking if n+1 element is the same as n. When using quicksort such approach would be with complexity O(n*log n + n/2). So basically my algorithm will be bound by sorting speed.