algorithm - Candidate in finding majority element in an array -

i not asking how find majority element in array, has been discussed @ length here find majority element in array

my problem below:

there array arr[1...2n], majority element of array maj, use following rule delete elements in arr,

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

then can new array new_arr, , candidate of majority element new_arr new_maj, there proof prove new_maj == maj?

yes there proof.

we interested in element pairs a[i],a[i+1], i odd. if a[i]=a[i+1], call such pair "good". other pairs "bad". elements equal majority candidate "groovy". pair of groovy elements groovy pair.

the simple fact pairs @ least 1 half of pairs groovy. suppose not so; among pairs, strictly less 1 half of elements groovy, , among bad pairs, no more 1 half of elements groovy. in total, strictly less 1 half of elements groovy. contradiction.

so have established @ least 1 half of pairs groovy.

now eliminate bad pairs. still @ least 1 half of elements groovy (because pairs remain, , among those, @ least 1 half groovy).

now eliminate every other element pairs. still @ least 1 half of elements groovy (because amount of each element halved).

this concludes proof.