# Find an index of the maximum occurring element with equal probability

Posted in

Vinay Khatri
Last updated on September 10, 2024

## Problem

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

#### Sample Input

`[1, 2, 1]`

#### Sample Output

`The index of maximum occurring number can be 0 or 2`

### Approach

The approach is to iterate through the array and find out the maximum occurring number and its frequency. Let the frequency be f . Then we generate a random number n between 1 and f and return the n th occurrence of the element. The maximum occurring element is also known as mode, according to statistics. This approach takes O(N) time.

#### C++ Programming

```#include<bits/stdc++.h>
using namespace std;
void solve(int arr[], int n)
{
unordered_map<int, int> freq;
for (int i = 0; i < n; i++)
freq[arr[i]] += 1;

int element;

int max_freq = INT_MIN;

for (pair<int, int> p : freq)
{
if (p.second > max_freq)
{
max_freq = p.second;
element = p.first;
}
}

int random = (rand() % max_freq) + 1;

for (int i = 0, occ = 0; i < n; i++)
{
if (arr[i] == element)
occ++;

if (occ == random)
{
cout << "Random occurrence is present "
"at index " << i << endl;
break;
}
}
}

int main()
{
int arr[] = {1, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
srand(time(NULL));

solve(arr, n);

return 0;
}
```

#### Output

`Random occurrence is present at index 2`

#### Java Programming

```import java.util.*;

class Solution
{

static void solve(int arr[], int n)
{
HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++)
if(mp.containsKey(arr[i]))
{
mp.put(arr[i], mp.get(arr[i]) + 1);
}
else
{
mp.put(arr[i], 1);
}

int element = Integer.MIN_VALUE;
int f = Integer.MIN_VALUE;
for (Map.Entry<Integer, Integer> p : mp.entrySet())
{
if (p.getValue() > f)
{
f = p.getValue();
element = p.getKey();
}
}

int random = (int) ((new Random().nextInt(f) % f) + 1);
for (int i = 0, occ = 0; i < n; i++)
{
if (arr[i] == element)
occ++;

if (occ == random)
{
System.out.print("Random occurrence is "
+"at index " + i +"\n");
break;
}
}
}

public static void main(String[] args)
{
int arr[] = {1, 2, 1};
int n = arr.length;
solve(arr, n);
}
}
```

#### Output

`Random occurrence is present at index 0`

#### Python Programming

```import random
def solve(arr, n):

mp = dict()
for i in range(n) :
if(arr[i] in mp):
mp[arr[i]] = mp[arr[i]] + 1

else:
mp[arr[i]] = 1

element = -10**9

max_freq = -10**9

for p in mp :

if (mp[p] > max_freq):
max_freq = mp[p]
element = p

r = int( ((random.randrange(1, max_freq, 2) % max_freq) + 1))

i = 0
occ = 0

while ( i < n ):

if (arr[i] == element):
occ = occ + 1

if (occ == r):

print("Random occurrence is at index " , i )
break
i = i + 1
arr = [1, 2, 1]
n = len(arr)
solve(arr, n)```

#### Output

`Random occurrence is present at index 2`

People are also reading: