Find an index of maximum occurring element with equal probability - GeeksforGeeks

Find an index of maximum occurring element with equal probability - GeeksforGeeks
Given an array of integers, find the most occurring element of the array and return any one of its indexes randomly with equal probability.

The idea is to iterate through the array once and find out the maximum occurring element and its frequency n. Then we generate a random number r between 1 and n and finally return the r’th occurrence of maximum occurring element in the array.

void findRandomIndexOfMax(int arr[], int n)

{

    // freq store frequency of each element in the array

    unordered_map<int, int> freq;

    for (int i = 0; i < n; i++)

        freq[arr[i]] += 1;

 

    int max_element; // stores max occurring element

 

    // stores count of max occurring element

    int max_so_far = INT_MIN;

 

    // traverse each pair in map and find maximum

    // occurring element and its frequency

    for (pair<int, int> p : freq)

    {

        if (p.second > max_so_far)

        {

            max_so_far = p.second;

            max_element = p.first;

        }

    }

 

    // generate a random number between [1, max_so_far]

    int r = (rand() % max_so_far) + 1;

 

    // traverse array again and return index of rth

    // occurrence of max element

    for (int i = 0, count = 0; i < n; i++)

    {

        if (arr[i] == max_element)

            count++;

 

        // print index of rth occurence of max element

        if (count == r)

        {

            cout << "Element with maximum frequency present "

                 "at index " << i << endl;

            break;

        }

    }

}

Read full article from Find an index of maximum occurring element with equal probability - GeeksforGeeks