public class Majority {
    public static void main(String args[]) {
        int[] arr = { 1, 1, 1, 2, 2, 1 ,2,2};
        Integer majority = divideAndCompute(arr, 0, arr.length - 1);
        System.out.println(majority == null ? "no majority" : majority);
    }

    public static Integer divideAndCompute(int[] arr, int low, int high) {
        if (low == high)
            return arr[low];
        if (low < high) {
            int mid = (low + high) / 2;
            int halfLengthOfSubArr = (high - low + 1) / 2;

            Integer majorityLeft = divideAndCompute(arr, low, mid);
            Integer majorityRight = divideAndCompute(arr, mid + 1, high);

            if (majorityLeft != null && majorityRight != null) {
                if (majorityLeft == majorityRight)
                    return majorityLeft;
                else {
                    if (count(arr, low, high, majorityLeft) > halfLengthOfSubArr)
                        return majorityLeft;
                    else if (count(arr, low, high, majorityRight) > halfLengthOfSubArr)
                        return majorityRight;
                    return null;
                }
            } else {
                // Implies left subArray has majority and right doesn't
                if (majorityLeft != null) {
                    return count(arr, low, high, majorityLeft) > halfLengthOfSubArr ? majorityLeft : null;
                } else if (majorityRight != null) {
                    return count(arr, low, high, majorityRight) > halfLengthOfSubArr ? majorityRight : null;
                }
                return null;
            }
        }

        return null;
    }

    public static int count(int[] arr, int low, int high, int target) {
        int count = 0;

        for (int i = low; i <= high; i++) {
            if (arr[i] == target)
                count++;
        }

        return count;
    }
}