Find an index of the maximum occurring element with equal probability

By | November 28, 2021

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 nth 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: 

Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published. Required fields are marked *