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

We have to use hashing to find these numbers which occur more than 10% of the time. It will take extra space, time complexity will be O(n).

Algorithm:-

function find_more_than_10_percent_numbers( input_array){

make a hashmap data structure to store elements and its frequency.

iterate though the whole array

    if the current element occurs already :
       increment its frquency by 1
   else:
       set its frquency to 1

iterate through the hahmap
    if frequency of the element > 10 % of input_array size:
        the element occurs more than 10% of time.

}

cpp code

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

void find_10_percent(int arr[], int size){

map<int , int> freq;

for (int i = 0; i < size; ++i)
{
if(freq.find(arr[i]) != freq.end()){
freq[arr[i]] +=1;
}else{
freq[arr[i]] = 1;

}
}

map<int ,int >::iterator iter = freq.begin();
  
for(; iter != freq.end(); ++iter)
{
int key = iter->first;
int value = iter->second;

if(value >= 0.1*size){
cout << key << \" occurs more than 10% of the time \"<< endl;
}
}
}

int main(int argc, char const *argv[])
{
int arr[] = {1,1,1,1,1,1,8,2,2,2,2,2,3,4,5,6,7,8,9,0,0,0,0,0,0, 6,6,6};

find_10_percent(arr, 28);
return 0;
}

}