Given an array arr[] and the two elements x and y, the task is to find which element(x or y) has highest occurrence in the array. If the occurrences are the same, then return the smaller element.
Examples:
Input: arr[] = {1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5}; x = 4, y = 5; Output: 4 Explanation: The occurrence of x in this array is = 4 times. The occurrence of y in this array is = 1 times. x has highest occurence than y, so we return 4. Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}; x = 1, y = 7; Output: 1 Explanation: The occurrence of x in this array is = 1 times. The occurrence of y in this array is = 1 times. both have same ocurrences, so we look for the smaller element. x = 1 is smaller than y = 7, so we return 1.
Approach:
- Traverse the whole array.
- Count the occurrences of x and y element.
- Check whether the count of x and y occurrences are the same, If they are the same then return the smaller element among x and y.
- Check which element(x or y) has the highest occurrence. If x has the highest occurrence then we return x, else we return y.
Below is the implementation of the above approach:
// Java program to find the element // with the highest occurrence in the array public class Cplusplus{ // Function to find the element with the // highest occurrence in the array. static int majorityElement(int[] a, int x, int y) { // Initialize the counter variable // x and y by zero. int count_x = 0; int count_y = 0; // Traverse the whole array. for(int i = 0; i < a.length; i++) { // Count the occurrence of x element. if(a[i] == x){ count_x++; } // Count the occurrence of y element. else if(a[i] == y){ count_y++; } } // If occurrences of x and y are same // then return smaller element among x and y. if(count_x == count_y){ return Math.min(x,y); } // Find the element which has highest occurrence // highest occurrence, If x has highest occurrence // then return x, else return y. else if(count_x > count_y) return x; else return y; } // Driver Code. public static void main(String args[]) { // Test Case 1: int arr1[] = {1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5}; int x1 = 4; int y1 = 5; System.out.println(majorityElement(arr1,x1,y1)); // Test Case 2: int arr2[] = {1, 2, 3, 4, 5, 6, 7, 8}; int x2 = 1; int y2 = 7; System.out.println(majorityElement(arr2,x2,y2)); } }
Output:
4 1
Time Complexity: O(N).