Majority element

gistfile1.java

public class MajorityElement {
	public static void main(String[] args) {
		System.out.println("Majority Element");
		int a[] = { 1, 3, 3, 1, 3 };
		printMajority(a);
	}

	private static void printMajority(int[] a) {
		int size = a.length;
		int element = findCandidate(a, size);

		if (isMajority(a, size, element))
			System.out.println(element);
		else
			System.out.println("NO Majority Element");
	}

	private static boolean isMajority(int[] a, int size, int cand) {
		int i, count = 0;
		for (i = 0; i < size; i++)
			if (a[i] == cand)
				count++;
		if (count > size / 2)
			return true;
		else
			return false;
	}

	private static int findCandidate(int[] a, int size) {
		int maj_index = 0, count = 1;

		for (int i = 1; i < size; i++) {
			if (a[maj_index] == a[i])
				count++;
			else
				count--;
			if (count == 0) {
				maj_index = i;
				count = 1;
			}
		}
		return a[maj_index];
	}
}