You are given an array of n numbers You have to find if ther

You are given an array of n numbers. You have to find if there is a number in the array that appears at least 10% of the time. (For example, if the array has 1000 elements, a number that appears 100 or more times.) Give an O(n) algorithm to find all such numbers that appear at least 10% of the time.

Solution

#include <iostream>
#include<map>
using namespace std;

int main()
{
    map<int,int> count;
    int n = 1000;
    int requiredCount = n*0.1;
  
    //Input the array
    int arr[n];
  
    //Traverse the array and store the count of element in the map
    for(int i=0;i<n++)
    {
        count[arr[i]] = count[arr[i]]+1;
    }
  
    map<int,int>::iterator it = count.begin();
  
    //Traverse the map and see if count exceeds the requiredCount which is 10% of n
    while(it!=count.end())
    {
        if(it->second >= requiredCount)
            cout << it->first << \" \";
    }
    return 0;
}