Monday, 16 September 2019

Majority Element Write a function which takes an array and prints the majority element (if it exists), otherwise prints “No Majority Element”. A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).



Examples :
Input : {3, 3, 4, 2, 4, 4, 2, 4, 4}
Output : 4 

Input : {3, 3, 4, 2, 4, 4, 2, 4}
Output : No Majority Element

// C#  program to find Majority 
// element in an array 
using System;
  
public class GFG{
          
// Function to find Majority element 
// in an array 
static void findMajority(int []arr, int n) 
    int maxCount = 0; 
    int index = -1; // sentinels 
    for(int i = 0; i < n; i++) 
    
        int count = 0; 
        for(int j = 0; j < n; j++) 
        
            if(arr[i] == arr[j]) 
            count++; 
        
          
        // update maxCount if count of 
        // current element is greater 
        if(count > maxCount) 
        
            maxCount = count; 
            index = i; 
        
    
      
    // if maxCount is greater than n/2 
    // return the corresponding element 
    if (maxCount > n/2) 
    Console.WriteLine (arr[index]); 
      
    else
    Console.WriteLine("No Majority Element"); 
  
// Driver code 
    static public void Main (){
          
        int []arr = {1, 1, 2, 1, 3, 5, 1}; 
        int n = arr.Length; 
      
        // Function calling 
        findMajority(arr, n); 
    }
//This code is contributed by Tushil.. 
}