0Problem 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)
- Initialize index and count of majority element
maj_index = 0, count = 1
- 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
- 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
