3
$\begingroup$

Here's a question about using a divide and conquer approach to find a majority element in an array. It's taken from Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Question 2.23. I'm not convinced why this algorithm should work.

enter image description here enter image description here

It seems to give no direction on what to do with the element that is left unpaired when the array size is odd. Take for example $A = [1, 1, 1, 2, 3]$.

Suppose we keep that unpaired singleton element at each step. For example, if we pair them up as $[1, 1], [1, 2], [3]$, then after keeping $1$, discarding $1, 2$, and keeping $3$, we're left with $1, 3$. Then we discard both since they're different, so we're left with no majority element.

Suppose we don't keep that unpaired singleton at each step. If we pair them up as $[1, 2], [1, 3], [1]$, then we must discard all of them, so again we're left with no majority element.

Where is the flaw? Can someone clarify whether this algorithm keeps or discards the unpaired singleton?

$\endgroup$
2
  • $\begingroup$ The algorithm assumes that $n$ is a power of 2. $\endgroup$ Jul 17 at 16:41
  • 7
    $\begingroup$ Please try to avoid posting text as images. Images aren't indexed with search engines, one can't easily copy text from an image and images are less accessible (blocked in certain places, doesn't work with screen readers and the font can't be customised). $\endgroup$ Jul 18 at 0:33
3
$\begingroup$

The algorithm as written assumes that $n$ is a power of 2. But you can adjust it to support odd-length arrays, while still completing in $O(n)$ time, as follows:

Suppose that at some given point in time, the array has odd length. Let $x$ be the last value in the array. You can determine whether $x$ is the majority element in $O(n)$. If so, return it. If not, then after discarding the last value in the array, it still has the same majority element, but now the number of elements is even.

$\endgroup$
1
$\begingroup$

When the size of your problem reduced to 2, it's the base case of your recursion, it's false that we pair up two remaining elements. so it's sufficiently, first count number of occurrence of two remaining elements in $A$.

for your problem we act as follow:

we check the whole array to count number of occurrence $A[i]=3$, and number of occurrence of $A[i]=1$ and then if number of occurrence $3\geq \frac{n}{2}+1$ or if number of occurrence $1\geq \frac{n}{2}+1$, we print it.

but the main problem is we must prove the correctness and running time of algorithm.

Suppose $\mathcal{X}$ is a majority element, because of, $\mathcal{X}$ is majority element, then the number of occurrence of it, is grater than $\frac{n}{2}$, so after pair up, at least there is one pair that elements are $\mathcal{X}$, otherwise it contradict with this fact that $\mathcal{X}$ is majority element.

On the other hand, at most all elements of array $A$ be $\mathcal{X}$, so both elements of a pair be equal, as a result at most half of the elements remain in each recursion.

Therefore one of the at most $\frac{n}{2}$ elements be $\mathcal{X}$. And we do our divide an conquer the problem until remain only two element.

Our statement holds only if $A$ contains $\mathcal{X}$. So after we get base that $n=2$, it's sufficient to for each of two remaining elements we check number of occurrence it.

Suppose the remaining elements is a,b:

    A,B=0
  for i = 1 to n
     if (a==A[i])
      A++
     if (b==A[i])
      B++

 if(a> n/2)
   print a
 else if (b> n/2)
   print b
 else
   print "there is no majority in the array"

Because of at each iteration at most half of the elements remain $$T(n)=T(\frac{n}{2})+O(n)$$ $$=O(n)$$

Note that at each iteration pairing up of $n$ elements need $O(n)$ time.

$\endgroup$
1
$\begingroup$

Not pointed out yet, but there is an online solution to the problem, even if it is not so easy to prove:

def majority(A):
  x:=A[1]
  c:=1
  for k from 2 to n:
    if A[k]=x:
      c++
    else:
      c--
      if c=0:
        x:=A[k]
        c:=1
  return x

To prove it correct, imagine that you maintain a set S of duplicate elements, and each time you see a new one you add it to S if it is another duplicate otherwise you pair it off with an element in S (and delete both). The above algorithm does that except by using a counter instead of actually keeping duplicates. Clearly, if an element m occurs more than half the time, it cannot be completely paired off, and so must remain undeleted at the end.

The algorithm is online because you can replace the array A by a generator (e.g. Python generator) and take only constant space.

$\endgroup$
1
  • $\begingroup$ Actually after writing the proof I feel it is easy to prove, but that may be just me. =P $\endgroup$
    – user21820
    Jul 18 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.