Find an element from a list that repeat more than N/3 times in Python

In this tutorial, we will find an element from a list that repeats more than N/3 times in Python. This question is asked in many interview/coding rounds.

Problem Statement for finding more than N/3 times repeated number from a list:

A list is given which is not sorted. The list is consists of only non-negative numbers.Return/Print a number whose occurrence is more than N/3 times.

Solve this question using constant space complexity and linear time complexity. Don’t use sort() to sort the list.

In case of multiple solutions, print/return anyone.

NOTE: Here N is the length of the list.

EXAMPLE:

INPUT:   A = [1,2,3,3,3,6,2]

OUTPUT:     3

EXPLANATION: 

Since N = 7 (length of list).So N/3 = 2.

Elements                 Frequency

1                                    1

2                                   2

3                                   3     (3>N/3)

6                                  1

So in the above Elements-Frequency table, as we can see, the Frequency of 3 is more than N/3 times. So the output will be 3.

Approaches to this type of problem will depend on the problem statement. Suppose if the sorted list is given, then we can solve this question using O(1) space complexity in linear time complexity via iterating through List and taking the record of the occurrence of each element.

But in the given statement some more condition is given like list is not sorted and we have to use only O(1) space complexity and linear time complexity. And we can not use sort() also.

So I will use Boyer–Moore majority vote algorithm for solving this problem more efficiently in linear time complexity and using only O(1) space complexity. By using, Boyer–Moore majority vote algorithm we can find desirable output without sorting the list.

Code for problem statement:

def repeat(l):
    c = 0
    d = 0
    n = len(l)/3
    # first and second(both or anyone) is in actual storing the most repeated number/element.
    first = -1                     
    second = -1
    for i in range(0,len(l)):
        if(first == l[i]):
            c = c+1
        elif(second == l[i]):
            d = d+1
        elif(c == 0):
            c = c+1
            first = l[i]
        elif(d == 0):
            d = d+1
            second = l[i]
        else:
            c = c-1
            d = d-1
    # after this for loop first or second anyone of both stored a element from list whose frequency is maximum.
    c = 0
    d = 0
    for j in range(0,len(l)):
        if(l[j] == first):
            c = c+1
            if(c>n):
                return(l[j])   # returning if first have frequency more than n(len(l)/3)
        elif(l[j] == second):
            d = d+1
            if(d>n):
                return(l[j])         # returning if second have frequency which is more than n(len(l)/3)
print(repeat([1,2,3,3,3,6,2])

OUTPUT:

3

My suggestion is to dry your code for more clarification about this algorithm. The dry run will sure help you guys to understand the concept more deeply.

Do comment if you like this content. You can also give any suggestions regarding this tutorial by commenting below.

Also, refer to these links for the more interesting concepts:

Python program to find maximum product quadruple in an array

Leave a Reply

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