Find an index of the maximum occurring element with equal probability

Posted in

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

Vinay Khatri
Last updated on May 22, 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:

    Leave a Comment on this Post

    0 Comments