Find an index of the maximum occurring element with equal probability

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:

• Find a Pair with the Given Sum in an Array
• Check if a subarray with 0 sum exists or not
• Convert a Binary Tree to Doubly Linked List
• Merge Sort for Linked Lists
• Maximum size square sub-matrices with all 1’s
• Bottom View of a Binary Tree
• Diameter of a Binary Tree
• Print Triangle Using * Character
• The Stock Span Problem
• Minimum Edit Distance