Finding a Majority Element

Problem Description Task.

The goal in this code problem is to check whether an input sequence contains a majority element.

Input Format. The first line contains an integer 𝑛, the next one contains a sequence of 𝑛 non-negative integers 𝑎0, 𝑎1, . . . , 𝑎𝑛−1. Constraints. 1 ≤ 𝑛 ≤ 10^5 ; 0 ≤ 𝑎𝑖 ≤ 10^9 for all 0 ≤ 𝑖 < 𝑛.

Output Format. Output 1 if the sequence contains an element that appears strictly more than 𝑛/2 times, and 0 otherwise.

Pseudo code

findCandidate(a[], size)

1.  Initialize index and count of majority element

     maj_index = 0, count = 1

2.  Loop for i = 1 to size – 1

    (a) If a[maj_index] == a[i]

          count++

    (b) Else

        count--;

    (c) If count == 0

          maj_index = i;

          count = 1

3.  Return a[maj_index]

Java Code

import java.util.Scanner;

// Moore- Voting algorithm . Run-time complexity O(n)

public class MajorityElement {

     public static void main(String[] args) {

           Scanner scan = new Scanner(System.in);

           int n = scan.nextInt();

           long array[] = new long[n];

           for (int i = 0; i < n; i++)

                array[i] = scan.nextLong();

           long candidate = findCandidate(array, n);

           System.out.println(candidate);

           int count = 0;

           for (int i = 0; i < n; i++)

                if (array[i] == candidate)

                     count++;

           if (count > (n / 2))

                System.out.println("1");

           else

                System.out.println("0");

     }

     static long findCandidate(long array[], int n) {

           int index = 0;

           long count = 1;

           for (int i = 1; i < n; i++) {

                if (array[index] == array[i])

                     count++;

                else

                     count--;

                if (count == 0)

                     {index = i;

                      count = 1;}

           }

           return array[index];

     }

}

Output:

10

2 124554847 2 941795895 2 2 2 2 792755190 756617003

2

1