## Wednesday, August 31, 2016

### 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``;`
`        ``}`
`    ``}`
`}`