6

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?

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
ali
  • 846
  • 2
  • 18
  • 34
  • Does is have to be a divide & conquer approach ? – gusbro Mar 01 '11 at 15:16
  • Yes I am looking for a divide and conquer algorithm. – ali Mar 01 '11 at 15:25
  • Is this homework? You were very close.... – Neil G Mar 01 '11 at 17:00
  • Yeah its homework. But I'm pretty stumped on how to continue from here. Any tips? – ali Mar 01 '11 at 17:13
  • I can do the lazy brute force by counting but that would defeat the purpose of getting an efficient algorithm. – ali Mar 01 '11 at 17:14
  • 2
    [Recent question](http://stackoverflow.com/questions/3740371/finding-the-max-repeated-element-in-an-array) about an O(_n_) algorithm for finding the element **if** the element exists. – aaz Mar 01 '11 at 18:01

3 Answers3

1

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.

Boris Pavlović
  • 63,078
  • 28
  • 122
  • 148
  • what do you mean send the x along with sub arrays? – ali Mar 01 '11 at 15:06
  • Instead of sending sub arrays like `aa ab bc ac` send tupples of sub array and the element `(aa, a), (ab, a), (bc, a), (ac, a)` – Boris Pavlović Mar 01 '11 at 15:08
  • ah i see. so that means the x that i am sending with the sub arrays will be a random element, or will it be the element that is in the subarray, in this example, aa – ali Mar 01 '11 at 15:11
  • it will be the element that is used to decide if the array is plural, ins't it? – Boris Pavlović Mar 01 '11 at 15:13
  • 2
    But we are not given the element. given an array, we are to find out if its plural and the plural element. – ali Mar 01 '11 at 15:23
1

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.

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
Agnius Vasiliauskas
  • 10,935
  • 5
  • 50
  • 70
  • Ah I see.. but assuming I can only compare the elements in the array based on equality. That is, I cannot determine if the elements are less than or more than each other. Also, would it be possible to have the algo be a divide and conquer type? – ali Mar 01 '11 at 16:19
  • Ok. Seems we can't use sorting approach with such requirements. What about this - build histogram of elements, if some element has relative frequency bigger then 0.5 - array is plural. Algo complexity will depend on histogram table lookup/insertion complexity. Or does this approach also violates no-less/greater-operators rule ? (because we still need to check does frequency bigger then 0.5) :-) – Agnius Vasiliauskas Mar 01 '11 at 20:28
  • if elements are comparable, algorithm is not bounded to sorting speed. – Saeed Amiri Mar 02 '11 at 12:10
  • I think we mis-understood each other. By saying bounded to sorting speed i mean that quick sort average complexity is n*log n which is greater then n/2. So main bottleneck is sorting speed of my suggested approach. – Agnius Vasiliauskas Mar 02 '11 at 17:18
  • I'd edited your answer and downvote removed, May be my edit is wrong, but I think you want say your algorithm bounded by sorting speed, not all algorithms. – Saeed Amiri Mar 03 '11 at 13:17
1

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.
Chris Nash
  • 2,941
  • 19
  • 22
  • Hi Chris! This is what i got so far. The requirement is for it to be a divide and conquer algorithm. So i will break the array into the subarrays of 2 elements. 'Compare the 2 elements, If EQUAL, store it in another array If NOT EQUAL, discard the 2 elements.' after going through all the elements, I will have an the new array. in the example i gave 'aa ab bc ac ===> results in having a in the new array.' but since there are only 4 a's in the array, it is not a plural array. thus, i would have to go through the array again to verify if that element is a plural element. – ali Mar 01 '11 at 19:16
  • so, will the O(n) of the verification bound the complexity of the algorithm? or would it be O(nlgn) due to the division stage of the algorithm. – ali Mar 01 '11 at 19:18
  • 1
    You are so close. You *will* always have to run over the array again to check. For example if your array is aaaabbbb, and you divide and conquer to aaaa|bbbb, those subarrays are plural (a and b), and you *have* to count a's and b's to verify neither is plural in the original. You were right, it's O(n lg n) - it's the verification step (verifying as many as n elements, at as many as lg n levels of subdivision). – Chris Nash Mar 01 '11 at 19:18
  • would it be correct to say, in your given example, aaaabbbb be divided into aa aa bb bb (array A). this gives a new array B - a a b b. from this array, we do the same as what we did in A, we get C - aa bb, and then we get a new array D - ab. Here we compare a and b, and since there are no more elements, we can return false and say the array is non-plural. – ali Mar 01 '11 at 19:32
  • 1
    I think you are trying to look too far down the "divide and conquer". aaaabbbb doesn't care about the 'leaf' nodes, it just cares about the two halves aaaa and bbbb and what their `findPluralElement()` would return. You only ever have to consider at most two candidates, not (n/2). – Chris Nash Mar 01 '11 at 19:38
  • i dont understand what you mean by "aaaabbbb doesnt care about the "leaf" nodes" So given any size n array, we would only split it into 2 halves? – ali Mar 01 '11 at 19:43
  • 1
    You *will* divide and conquer all the way down to 1 or 2 elements... but any results you get there won't bubble all the way to the top. Your set of size 8 doesn't need to have the sets of size 2 to work with. The best way I could explain this would be just to write the answer... but that wouldn't be fair ;) – Chris Nash Mar 01 '11 at 19:50