using System;

using System.Collections.Generic;

​

//Given an unsorted array which has a number in the majority (a number appears more than 50% in the array), 

//find that number?

public class Program

{

    public static void Main()

    {

        //Console.WriteLine("Hello World");

        Console.WriteLine("majority Number in the given array is:" + majorityNumberFromArray(new int[]{ 1, 3, 4, 5, 5, 5, 5}));

    }

    public static int majorityNumberFromArray(int[] unsortedArray)

    {       

        /*******pseudo code*********    

        Create a Dictionary to store the count of the elements present in the unsortedArray

        for each element in unsortedArray 

            if the element is not present in the Dictionary

                insert 1 

            else

                increment value corresponding to the key in the dictionary by 1

                if that value is greater than the majority (arrayLength/2) 

                    return that key

        throw exception("such number does not exist")           

        */

        if(unsortedArray == null || unsortedArray.Length ==0)

            throw new Exception("the input array is either null or has no elements"); 

        Dictionary<int, int> elementCountDict = new Dictionary<int, int>();

        foreach (int x in unsortedArray)

        {

          if(elementCountDict.ContainsKey(x))

          { 

            //  Console.WriteLine("x:"+ x + " majorityLimit: "+ unsortedArray.Length/2 + " value: " + elementCountDict[x]);

              elementCountDict[x] += 1;

              if(elementCountDict[x] > unsortedArray.Length/2)

              {               

                  return x;

              }

          }

          else

          {

              elementCountDict.Add(x, 1);

          }         

        }

        throw new Exception("such number does not exist in the given array");

    }

}