Candidate in finding majority element in an array

Question

I am not asking how to find the majority element in an array, which has been discussed at length here Find majority element in array

My problem is as below:

There is an array arr[1...2n], the majority element of this array is maj, now I will use the following rule to delete elements in arr,

if arr[i] == arr[i + 1], delete arr[i], i = 1, 3, 5,..., 2n - 1; else if arr[i] != arr[i + 1], delete both arr[i] and arr[i + 1], i = 1, 3, 5, ..., 2n - 1.

then we can get a new array new_arr, and candidate of the majority element for new_arr is new_maj, is there any proof to prove that new_maj == maj?

Answer 1

Here's my variant of the proof:

Consider the 4 cases for pairs arr[i] and arr[i+1] (or vice versa, order with the pair is not important), i is odd. Let maj be the major element and min is any minor element:

1. maj maj - let the number of such pairs be a
2. maj min - let the number of such pairs be b
3. min1 min2 - let the number of such pairs be c, min1 != min2
4. min1 min1 - let the number of such pairs be d

a, b, c, d are all >= 0.

Case 1 contributes 2 to the original sum of major elements |maj| and decreases the final sum of major elements |maj|' (after execution of the algorithm) by 1

Case 2 contributes 1 to |maj| and 1 to |min|, the original sum of all minor elements, and decreases |maj|' by 1 and |min|' by 1

Case 3 contributes 2 to |min| and decreases |min|' by 2

Case 4 contributes 2 to |min| and decreases |min|' by 1

Therefore, the total number of major elements in the original array arr[] is:

|maj| = 2a + b

While the number of all minor elements is:

|min| = b + 2c + 2d

Since |maj| > |min| ,

2a + b > b + 2c + 2d
    2a > 2c + 2d
     a > c + d

After running the algorithm, the new number of major elements is given by:

|maj|' = |maj| - a - b

and the new number of minor elements is:

|min|' = |min| - b - 2c - d

Substituting we get:

|maj|' = 2a + b - a - b           = a
|min|' = b + 2c + 2d - b - 2c - d = d

Since we know from above that c + d < a, and a, c, d are all >= 0, we have

a > c + d =>
a > d =>
|maj|' > |min|'

Therefore maj is still the major element in the new array.

Answer 2

Yes there is a proof.

We are only interested in element pairs a[i],a[i+1], i odd. If a[i]=a[i+1], we call such a pair "good". Other pairs are "bad". Elements that are equal to the majority candidate are "groovy". A good pair of groovy elements is a groovy pair.

The simple fact about good pairs is that at least one half of good pairs are groovy. Suppose it is not so; then among good pairs, strictly less than one half of elements are groovy, and among bad pairs, no more than one half of elements are groovy. In total, strictly less than one half of elements are groovy. This is a contradiction.

So we have established that at least one half of good pairs are groovy.

Now eliminate all bad pairs. Still at least one half of all elements are groovy (because only good pairs remain, and among those, at least one half are groovy).

Now eliminate every other element from good pairs. Still at least one half of all elements are groovy (because amount of each element is simply halved).

This concludes the proof.

Answer 3

Define N = 2 n. The array contains N elements.

Define M as the number of times maj appears in the array. The definition of “majority element” is that M > N/2.

Now divide the array into pairs p[1] ... p[n]. Define q0 as the number of pairs that contain zero instances of maj. Define q1 as the number of pairs that contain exactly one instance of maj. Define q2 as the number of pairs that contain exactly two instances of maj.

Then N = 2 q0 + 2 q1 + 2 q2 and M = q1 + 2 q2.

Substitute into the inequality defining the majority element, and simplify:

        M > N / 2
q1 + 2 q2 > (2 q0 + 2 q1 + 2 q2) / 2
q1 + 2 q2 > q0 + q1 + q2
     2 q2 > q0 + q2
       q2 > q0

So the number of pairs containing two instances of maj exceeds the number of pairs containing zero instances of maj.

Now define M' to be the number of times maj appears in the new array, after running your algorithm. The algorithm deletes one maj for each q1 pair, and one maj for each q2 pair. So M' = M - q1 - q2.

Define N' to be the size of the new array produced by the algorithm. The algorithm deletes two elements for each q1 pair, and one element for each q2 pair.

But we don't know how many elements the algorithm deletes for each q0 pair. Some of the q0 pairs contain two different elements, and the algorithm deletes both. But the other q0 pairs contain identical (non-maj) elements, and the algorithm deletes only one.

One extreme is that all of the q0 pairs are deleted entirely. In that case, the algorithm deletes 2 q0 elements, so

N - 2 q1 - q2 - 2 q0 ≤ N'

The other extreme is that only one element is deleted from each q0 pair. In that case, the algorithm deletes q0 elements, so

N - 2 q1 - q2 - q0 ≥ N'

Let's go back to the definition of “majority element” and do some algebra:

          M > N / 2
M - q1 - q2 > N / 2 - q1 - q2
M - q1 - q2 > (N - 2 q1 - 2 q2) / 2
M - q1 - q2 > (N - 2 q1 - q2 - q2) / 2

The left-hand side is M'.

M' > (N - 2 q1 - q2 - q2) / 2

Can we turn the right-hand side into N' / 2? First, multiply both sides by 2:

2 M' > N - 2 q1 - q2 - q2

Recall that we proved q2 > q0. Therefore

2 M' > N - 2 q1 - q2 - q2 > N - 2 q1 - q2 - q0

and, since we deduced N - 2 q1 - q2 - q0 ≥ N',

2 M' > N - 2 q1 - q2 - q0 ≥ N'

so

2 M' > N'
  M' > N' / 2

Thus maj appears sufficient times in the new array to be the majority element of the new array. QED.