title: Find the number in an array which occurred most number of times
body: <p>Given an integer array, i need to find which number occurred most number of times.
  I have written algorithm as below.</p>
  
  <blockquote>
    <ol>
    <li><p>Use a map to store number and number of times it occurred.</p>
    
    <p><code>map&lt;int, int&gt;</code></p>
    
    <p>Key: represents the number<br>
    value: represents number of times key occurred.</p></li>
    <li>Scan input array and update the map with number and number of occurances.</li>
    <li>Iterate through map from the begining to end. Find the key for
    which maximum value is present. This
    key becomes the number which occurred
    most number of times.</li>
    </ol>
  </blockquote>
  
  <p>I implemented the algorithm as below.</p>
  
  <pre><code>#include &lt;iostream&gt; 
  #include &lt;map&gt;
  using namespace std; 
  int main()
  {
      int a[10] = {1,2,3,2,1,3,2,4,1,1}; //Input array: hardcoded for testing
      map&lt;int, int&gt; m;
  
      for(int i=0;i&lt;10;i++)
      {
          m[a[i]]++;  //Increment the value of key for counting occurances
      }
  
      int mostNumTimes = 0; 
      int number = -999; //-999 represents invalid number
      map&lt;int,int&gt;::iterator it = m.begin();
      for( ;it != m.end(); it++)  //Find the number which occurred 
      {                           //most number of times
          if(it-&gt;second &gt; mostNumTimes)
          {
              mostNumTimes = it-&gt;second;
              number = it-&gt;first;
          }
      }
      if(number != -999)   //Print number and number of times it occurred
      {
          cout&lt;&lt;"Number: "&lt;&lt;number&lt;&lt;endl;
          cout&lt;&lt;"Number of times occured: "&lt;&lt;mostNumTimes&lt;&lt;endl;
      }
      else
      {
          cout&lt;&lt;"Input array is empty"&lt;&lt;endl;
      }
      return 0;
  }
  </code></pre>
  
  <blockquote>
    <p>Output:  </p>
    
    <p>Number: 1  </p>
    
    <p>Number of times occured: 4</p>
  </blockquote>
  
  <p>Question: Are there any optimal ways of doing it ?
  In the end, i am iterating through entire map as I couldn't find any member function for finding key whose value is highest in map. can i avoid iterating all keys ?</p>
  
  <p>Note: I am not considering if multiple numbers occuring same number of times. I am finding first number with most occurances.</p>