The Interview Question Today#11(6-3-19)

Question:
Find a majority element in an array of size n

Examples :

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

Approach:
int majorityElementNaive(int A[], int n)
{
// check if A[i] is majority element or not
for (int i = 0; i <= n/2; i++)
{
int count = 1;
for (int j = i + 1; j < n; j++) {
if (A[j] == A[i]) {
count++;
}
}

if (count > n/2) {
return A[i];
}
}

return -1;

}

C program: 
#include<stdio.h>
// Function to find Majority element in an array
void findMajority(int arr[], int n)
{
    int i,j;
    int maxCount = 0;
    int index = -1; // sentinels
    for( i = 0; i < n; i++)
    {
        int count = 0;
        for( 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)
       printf("Majority Element=%d\n",arr[index]);

    else
        printf("No Majority Element");
}

int main()
{
    int arr[100];
    int n,i;
    printf("Enter the Number of Elements present: ");
    scanf("%d",&n);
    printf("\nEnter the values of Elements");
    for(i=0;i<n;i++)
    {
        printf("\nElements %d:",i+1);
        scanf("%d",&arr[i]);
    }

    findMajority(arr, n);

    return 0;
}
Output:
Enter the Number of Elements present: 5

Enter the values of Elements
Elements 1:1

Elements 2:2

Elements 3:1

Elements 4:2

Elements 5:1
Majority Element=1