Given a Sorted Array of n integers, and an Integer X, the task is to find whether the given Integer X appears more than n/2 times in the array or not.
Input: arr[] = {1,1,2,3,3,3,3,3,3,3,3,3,4,5,6,6,7}, x=3
Output: 3 occurs 9 times which is more than 8 times
Input: arr[] = {1,1,2,3,3,3,3,3,3,3,3,3,4,5,6,6,7}, x=6
Output: 6 doesn't occur more than 8 times
Approach #1:
- Maintain a count variable, initialize it with 0.
- Iterate over the array and compare each element with x, if it is equal to x, then increment the count.
- After iterating over the whole array check whether the value of the count variable is greater than n/2(half of the length of the array) or not.
- If the value of the count variable is greater than n/2, print “true” else false.
Below is the implementation of the above approach:
Java
// Java Program to check whether element// x occurs more than n/2 times or notclass GFG { static boolean isOccurMoreThanHalfTimes(int arr[], int x) { int len = arr.length; // initialize the count by 0 int count = 0; for (int i = 0; i < len; i++) { // if x is equal to arr[i],increment the count if (arr[i] == x) count++; } // checking the value of count variable if (count > len / 2) return true; else return false; } public static void main(String[] args) { // driver code int arr[] = { 1, 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 5, 6, 6, 7 }; int x = 3; // calling the function and storing // the returned result boolean answer = isOccurMoreThanHalfTimes(arr, x); if (answer) { System.out.println("true"); } else { System.out.println("false"); } }} |
Output
true
- Time Complexity- 0(N)
- Space Complexity: 0(1)
Approach #2:
- Use a lower bound function for finding a lower bound index in a sorted array.
- Use an upper bound function for finding an upper bound index in a sorted array.
- Find the difference between the upper and lower bound index.
- If the difference is greater than N/2 then print occurs more than N/2.
- Else print doesn’t occur more than N/2 times.
Below is the implementation of the above approach:
Java
class Main { public static int lower_bound(int arr[], int low, int high, int X) { // Base Case if (low > high) { return low; } // Find the middle index int mid = low + (high - low) / 2; // If arr[mid] is greater than // or equal to X then search // in left subarray if (arr[mid] >= X) { return lower_bound(arr, low, mid - 1, X); } // If arr[mid] is less than X // then search in right subarray return lower_bound(arr, mid + 1, high, X); } // Recursive implementation of // upper_bound public static int upper_bound(int arr[], int low, int high, int X) { // Base Case if (low > high) return low; // Find the middle index int mid = low + (high - low) / 2; // If arr[mid] is less than // or equal to X search in // right subarray if (arr[mid] <= X) { return upper_bound(arr, mid + 1, high, X); } // If arr[mid] is greater than X // then search in left subarray return upper_bound(arr, low, mid - 1, X); } // Function to implement lower_bound // and upper_bound of X public static int printBound(int arr[], int N, int X) { int lower, upper; // If lower_bound doesn't exists if (arr[0] == X) { lower = 0; } else { // Find lower_bound lower = lower_bound(arr, 0, N, X); } // If upper_bound doesn't exists if (arr[N - 1] == X) { upper = N - 1; } else { // Find upper_bound upper = upper_bound(arr, 0, N, X); } return upper - lower; } public static void main(String[] args) { int X = 3; int arr[] = { 1, 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 5, 6, 6, 7 }; int occurrence = printBound(arr, arr.length, X); if (occurrence >= arr.length / 2) { System.out.println( X + " occurs " + occurrence + " times which is more than " + arr.length / 2 + " times"); } else { System.out.println(X + " doesn't occur more than " + arr.length / 2 + " times"); } }} |
Output
3 occurs 9 times which is more than 8 times
Time Complexity: O(log n)
