Help regarding ALC006

https://www.codechef.com/ALCM2019/problems/ALC006/

I implemented a solution where I used probabilistic analysis. Basically, if there is a majority element in the range, then probability of picking that element randomly would be >1/2. So if I try picking a random element for k number of times, the probability of not picking the major element would be (1/2)^k. Letting k to be big enough reduces the probability of not recognizing major element to almost zero.

However, I had seen a few solutions with segment tree in which they find the majority element. Could someone explain the logic behind it?

1 Like

Answering my own question,
found the exact problem in one of previous contests. The editorial for that problem: CHEFLKJ - Editorial .

2 Likes