Problem Statement: Write a function to find if a given integer x appears more than n/2 times in a sorted array of n integers.
Basically, we need to write a function say isMajority() that takes an array (arr[] ), the array’s size (n) and a number to be searched (x) as parameters and returns true if x is a majority element (present more than n/2 times).
Examples:
Input: arr[] = {1, 2, 3, 3, 3, 3, 10}, x = 3
Output: True (x appears more than n/2 times in the given array)
Input: arr[] = {1, 1, 2, 4, 4, 4, 6, 6}, x = 4
Output: False (x doesn't appear more than n/2 times in the given array)
Input: arr[] = {1, 1, 1, 2, 2}, x = 1
Output: True (x appears more than n/2 times in the given array)
Method 1: Using linear search
Linearly search for the first occurrence of the element, once you find it (let at index i), check the element at index i + n/2. If the element is present at i+n/2 then return 1 else return 0.
C#
// C# Program to check for majority// element in a sorted array using System;class GFG { static bool isMajority(int[] arr, int n, int x) { int i, last_index = 0; // Get last index according to // n (even or odd) last_index = (n % 2 == 0) ? n / 2 : n / 2 + 1; // Search for first occurrence // of x in arr[] for (i = 0; i < last_index; i++) { // Check if x is present and // is present more than n/2 times if (arr[i] == x && arr[i + n / 2] == x) return true; } return false; } // Driver code public static void Main() { int[] arr = { 1, 2, 3, 4, 4, 4, 4 }; int n = arr.Length; int x = 4; if (isMajority(arr, n, x) == true) Console.Write(x + " appears more than " + n / 2 + " times in arr[]"); else Console.Write(x + " does not appear more than " + n / 2 + " times in arr[]"); }}// This code is contributed by Sam007 |
Output:
4 appears more than 3 times in arr[]
Time Complexity: O(n)
Auxiliary Space: O(1), as constant extra space is used.
Method 2: Using Binary Search
Use binary search methodology to find the first occurrence of the given number. The criteria for binary search is important here.
C#
// C# Program to check for majority// element in a sorted array */using System;class GFG { // If x is present in arr[low...high] // then returns the index of first // occurrence of x, otherwise returns -1 static int _binarySearch(int[] arr, int low, int high, int x) { if (high >= low) { int mid = (low + high) / 2; // low + (high - low)/2; // Check if arr[mid] is the first // occurrence of x. arr[mid] is // first occurrence if x is one of // the following is true: // (i) mid == 0 and arr[mid] == x // (ii) arr[mid-1] < x and arr[mid] == x if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x)) return mid; else if (x > arr[mid]) return _binarySearch(arr, (mid + 1), high, x); else return _binarySearch(arr, low, (mid - 1), x); } return -1; } // This function returns true if the x is // present more than n/2 times in arr[] // of size n static bool isMajority(int[] arr, int n, int x) { // Find the index of first occurrence // of x in arr[] int i = _binarySearch(arr, 0, n - 1, x); // If element is not present at all, // return false if (i == -1) return false; // check if the element is present // more than n/2 times if (((i + n / 2) <= (n - 1)) && arr[i + n / 2] == x) return true; else return false; } // Driver code public static void Main() { int[] arr = { 1, 2, 3, 3, 3, 3, 10 }; int n = arr.Length; int x = 3; if (isMajority(arr, n, x) == true) Console.Write(x + " appears more than " + n / 2 + " times in arr[]"); else Console.Write(x + " does not appear more than " + n / 2 + " times in arr[]"); }}// This code is contributed by Sam007 |
Output:
3 appears more than 3 times in arr[]
Time Complexity: O(Logn)
Auxiliary Space: O(1), as constant extra space is used.
Method 3: Divide and Conquer
If it is already given that the array is sorted and there exists a majority element, checking if a particular element is as easy as checking if the middle element of the array is the number we are checking against.
Since a majority element occurs more than n/2 times in an array, it will always be the middle element. We can use this logic to check if the given number is the majority element.
C#
using System;// Classclass GFG { // Method to find majority element static bool isMajorityElement(int[] arr, int n, int key) { if (arr[n / 2] == key) return true; else return false; } // Driver Code public static void Main(String[] args) { // Custom input array int[] arr = { 1, 2, 3, 3, 3, 3, 10 }; int n = arr.Length; int x = 3; if (isMajorityElement(arr, n, x)) Console.Write(x + " appears more than " + n / 2 + " times in []arr"); else Console.Write(x + " does not appear more " + "than " + n / 2 + " times in arr[]"); }}// This code is contributed by aashish1995 |
3 appears more than 3 times in arr[]
Time complexity: O(1)
Auxiliary Space: O(1)
Method 4: Using Moore’s Voting Algorithm
- Initialize the candidate element as the first element of the array setting count to 1.
- Traverse through the array from the second element to the last.
- If the current element is the same as the candidate element, increment the count otherwise decrement the count.
- If the count becomes 0, set the current element as the candidate element and reset the count to 1.
- Check if the candidate element is the majority element by traversing the array again and counting the number of occurrences of the candidate element.
- If the number of occurrences of the candidate element is greater than n/2, return the candidate element. Otherwise, return -1.
C#
using System;// Classclass Program { // Method to find majority static int FindMajority(int[] arr, int n) { // Initialize candidate as first element int candidate = arr[0]; int count = 1; // Find majority element for (int i = 1; i < n; i++) { if (arr[i] == candidate) count++; else count--; if (count == 0) { candidate = arr[i]; count = 1; } } // Checking if candidate is the majority element int countCandidate = 0; for (int i = 0; i < n; i++) { if (arr[i] == candidate) countCandidate++; } if (countCandidate > n / 2) return candidate; else return -1; } // Driver method static void Main() { // Custom input array int[] arr = { 1, 2, 3, 3, 3, 3, 10 }; int n = arr.Length; int majorityElement = FindMajority(arr, n); // Printing the majority element // it is found if (majorityElement != -1) Console.Write(majorityElement + " is the majority element"); else // Display message there exists no majority // element Console.Write("No majority element"); }} |
3 is the majority element
Time complexity is O(n)
Auxiliary Space: O(n)
Please refer complete article on Check for Majority Element in a sorted array for more details!
