class Solution {
    public int majorityElement(int[] nums) {
        
        if(nums.length == 2) return nums[0]; 
        // as there are only two elements in array, and majority element must be present so if n/2 = 1 , so majority element should be greater than 1 time.
        
        else{
            return checkRecursive(nums, 0, nums.length - 1);
        }
    }
    
    public int checkRecursive(int[] arr, int start, int end){
        
        if(start == end) return arr[start];
        
        int mid = (start+end) / 2;
        
        int left_half = checkRecursive(arr, start, mid);
        int right_half = checkRecursive(arr, mid+1, end);
        
        if(left_half == right_half) {
            return left_half;
        }
        
        else{
            
            int leftCount = occurrence(arr, left_half, start, end);
            int rightCount = occurrence(arr, right_half, start, end);
            
            return leftCount > rightCount ? left_half : right_half;
        }
    }
    
    public int occurrence(int[] arr, int pos, int start, int end){
        
        int count = 0;
        
        for(int i=start; i <= end; i++){
            
            if(arr[i] == pos){
                count++;
            }
        }
        return count;
    }
}