# Selection of Majority in O(n)

Selection algorithms are very useful in many instances, like finding the majority. Given an array of size n that contains a majority item (an item that’s repeated more than n/2 times), we can find that item in O(n). Basically, we can consider it as a voting process, each occurrence is a vote and each item is a candidate. Since there’s a constant pool of votes, each candidate is winning a vote when it appears and losing a vote when another candidate is appearing instead. If the number of votes becomes 0, then it’s time to pick another candidate. The candidate with a positive number of votes is the majority. Using this algorithm doesn’t require extra storage like a hash to store the frequency of each item, we just need an integer for storing the frequency and a variable to store the candidate. Here’s a sample in C# that prints the majority in an array of integers:

using System;

namespace ConsoleApplication1
{

class Program

{

static void Main(string[] args)

{

int[] array = new int[] { 2, 1, 5, 1, 7, 1, 9, 1 };

int candidate = array[0], freq = 1;

for (int i = 1; i < array.Length; ++i)

{

freq += (candidate == array[i] ? 1 : 1);

if (freq == 0)

{

candidate = array[i];

freq = 1;

}

}

Console.WriteLine(“Majority: ” + candidate);

}

}
}