search

OpenGenus / cosmos

World's largest Contributor driven code dataset | Used in Quark Search Engine, @OpenGenus IQ, OpenGenus Visual Project
http://internship.opengenus.org
GNU General Public License v3.0
13.56k stars 3.67k forks source link

Majority Element Algorithm using randomization #6606

Open Ananyapam7 opened 1 year ago

Ananyapam7 commented 1 year ago

This is O(n):

Details:

The current implemented algorithm which finds the majority element of an array is the Moore-Voting algorithm. However, there are a few other ways to solve this problem which I believe must be a part of this repository. One of them is using a randomized algorithm. On average it has the same runtime, but when the size of the array increases exponentially, this algorithm is much much faster probabilistically.

The majority element of a vector is an element which occurs with a frequency more than floor(n/2). So you have more than a 50% chance of picking out the majority element in your first try if you pick any element randomly.

Suppose you don't find the majority element in your first try. You can then pick a random element again and check if it is a majority element. You do this until you eventually find the majority element.

The algorithm is verifiably correct because we ensure that the randomly chosen value is the majority element before ever returning. I believe that this algorithm must be a part of this repository

Ananyapam7 commented 1 year ago

I have submitted the pull request #6607 for this issue as a part of the Hacktoberfest 2022.