using System;

using System.Linq;

using System.Collections.Generic;

​

/*

​

****************This is optimized Solution *****************

​

Link: [https://www.scaler.com/academy/mentee-dashboard/class/23419/assignment/problems/2?navref=cl_tt_nv]

Problem Description

​

Given an array of size N, find the majority element. The majority element is the element that appears more than floor(n/2) times.

You may assume that the array is non-empty and the majority element always exists in the array.

​

​

​

Problem Constraints

1 <= N <= 5*105

1 <= num[i] <= 109

​

​

Input Format

Only argument is an integer array.

​

​

Output Format

Return an integer.

​

​

Example Input

[2, 1, 2]

​

​

Example Output

2

​

​

Example Explanation

2 occurs 2 times which is greater than 3/2.

​

*/                  

public class Program

{

    private static int findMajorityElement(List<int> A)

    {

        long maxElem = A[0]; int arrCount = A.Count; int maxCount = 1; int minNByTwo = arrCount / 2;

        for(var i = 1; i < arrCount; i++){

            if(A[i] == maxElem) {

                maxCount++;

            }else{

                maxCount--;

            }

            if(maxCount == 0){ maxElem = A[i]; maxCount++; } 

        }

        //This for Loop is to ensure maxElem frequency is > (N / 2)

        maxCount = 0;

        for(var j = 0; j < arrCount; j++){

            if(A[j] == maxElem) { maxCount++; }

        }

        maxElem = (maxCount > minNByTwo) ? maxElem : 0;

        return (int)maxElem;

    }

    public static void Main()

    {

        List<int> elemArray = new List<int>() { 2, 1, 2};

        int getMajorityElem = Program.findMajorityElement(elemArray);

        Console.WriteLine(getMajorityElem);

    }

}