Find an Index of Maximum Occurring Element with Equal Probability using Python

Introduction:

In this tutorial, we learn how to find an index of maximum occurring element with equal probability using Python. If we take an input as {1, 2, 5, 3, 4, 5, 6, 5, 7, 8, 5, 9} here, 5 is taken in four times. The index number 5 is 2, 5, 7 and 10. Here, we are given a solution that returns an index of the maximum occurring element with equal probability. If the array has two largest occurrences, the solution should consider the first largest occurrence.

Example:

Here, give an example of array index input and its corresponding output.

Input: 
arr[] = [1, 2, 5, 3, 4, 5, 6, 5, 7, 8, 5, 9]

Output:  
5 is the element with maximum frequency, which is present at the 2nd index.
OR
5 is the element with maximum frequency, which is present at the 5th index.
OR
5 is the element with maximum frequency, which is present at the 7th index.
OR
5 is the element with maximum frequency, which is present at the 10th index.

All of these above outputs have equal probability.

Algorithm:

Here, we learn the algorithm to find an index of maximum occurring element with equal probability using Python.

Firstly, define the function findIndexOfMaxElement with two parameters, which are arr and n
Then, keep the count of all input elements on the map.
Now, we create a for loop.
Then, traversing this map.
After that, we need to find which element first occurs in maximum time.
Then, generate an "n" random number between 1 and count the element occurring at maximum time in the map.
Now we initialize the array input arr[]
Lastly, traversing the input. Then, it returns the nth occurrence of the maximum occurring element's index value.

Program code:

Here, we give the program code in Python to find an index of maximum occurring element with equal probability. The code is now given below -

# Used Python to find an index of the maximum occurring element with equal probability.
# Import the random library
import random
 
# Define the function findIndexOfMaxElement with two parameters: arr and n
# It randomly finds the maximum occurring element's index value from the array.
def findIndexOfMaxElement(arr, n):
   
# Here, the map is equalized with the dict()
map = dict()

# Now create a for loop here
for i in range(n):
        if(arr[i] in map):
            map[arr[i]] = map[arr[i]] + 1
        else:
            map[arr[i]] = 1
         
   
max_element = -323567
# Maximum occurring element stored here
# The maximum occurring element's count is stored here
   
max_so_far = -323567
 
# Then, traversing this map and finding which element is first occurring in maximum time. 
for p in map:
    
        if (map[p] > max_so_far):
            max_so_far = map[p]
            max_element = p
         
   
# Here, a random number k is generated between [1, max_so_far]
k = int( ((random.randrange(1, max_so_far, 2) % max_so_far) + 1))
i = 0
count = 0
# Again traverse the array, which returns the index of kth occurrence of max element
   
while ( i < n ):
    
        if (arr[i] == max_element):
            count = count + 1
 
        # Here prints the index of kth occurrence of max element
        if (count == k):
         
            print("5 is the element with maximum frequency, which is present at index: " , i )
            break
        i = i + 1
    
# Initialize the array input arr[]
arr = [1, 2, 5, 3, 4, 0, 5, 6, 5, 7, 8, 5, 9]
# Find the length of the array and store it in n
n = len(arr)

findIndexOfMaxElement(arr, n)

Output:

Now, we compile the above code in Python, and after successful compilation, we run it. The output is given below -

5 is the element with maximum frequency, which is present at index:  11

Conclusion:

So, in this tutorial, we are learning how to find an index of maximum occurring elements with equal probability using Python. Mainly here, we check which element occurs the maximum time in the given map and then find the maximum occurrence element index value randomly. We also learn the algorithm of this program. Depending upon this algorithm, we write the above Python code and share its output.

Next TopicFinite Automata Algorithm for Pattern Searching Using Python

← prev next →