Given an array of size n and a number k, find all elements that appear more than n/k times.

Introduction

The main aim of this problem is that we are given an array of elements where we can have an array of elements repeated more than once. We are also provided with a ‘k’ value along with that array. Then we need to find or return all the elements in the array that appear more than n/k times. We will look over this problem in this article.

Solution

Approach

For this problem, we can make use of a hash table or dictionary. We will assign the key as the array element and the value as its frequency. For example: 
Array = [1,3,3,2,2,5,2,3] and say k value as 4.
Then, in this case, we will get the output as [2,3]. Because, here n = number of array elements, i.e., n=8 and k=4. Therefore we need to find all the array elements that appear more than 8/4, i.e., two times. So, in the array, we have 2 and 3 that appear 3times and 3times, respectively, greater than two times. Thus, we got output as [2,3].
We can get intermediate dictionary form as follows:
Dictionary = {1: 1, 2: 3, 3: 3, 5: 1}
Then we will compare each element’s frequency with the n/k value. If any element’s frequency is greater than n/k, we will output that element. This is a simple and complete approach.
Simple Tracing of the approach for the above approach:

Input: [1,3,3,2,2,5,2,3], k

Output: 

2

3

Step1: Initialize an empty dictionary, d = { }

Step2:

1. Traverse through the array. If the element is not in the dictionary, add it to the dictionary and its value as 1.
2. If not, increment the value of the element by one.
3. Repeat this until all the elements of the array are covered.

For element 1, 1 is not in d. Then, add 1 with value 1 to d. So,        d = {1: 1}

For element 3, 3 is not in d. Then, add 3 with value 1 to d. So,        d = {1: 1, 3: 1}

For element 3, 3 is in d with value1. So on inc by 1, we will get d:   d = {1: 1, 3: 2}

For element 2, 2 is not in d. Then add 2 with value 1 to d. So,         d = {1: 1, 3: 2, 2: 1}

For element 2, 2 is in d with value1. So on inc by 1, we will get d:   d = {1: 1, 3: 2, 2: 2}

For element 5, 5 is not in d. Then, add 5 with a value of 1 to d. So, d = {1: 1, 3:2, 2:2, 5:1}

For element 2, 2 is in d with value2. So on inc by 1, we will get d:   d = {1: 1, 3: 2, 2: 3, 5:1}

For element 3, 3 is in d with value2. So on inc by 1, we will get d:   d = {1: 1, 3: 3, 2: 3, 5:1}

After building this dictionary, we will traverse this dictionary. If an element’s value is greater than n/k, we will print that value to the output.

Code

Python

def findSol(arr, k):

    x = len(arr)//k   #Calculating the n/k value.

    d = {}  #intializing an empty dictionary.

    for i in arr:       #iterating through the array to build frequency dictionary.

        if i not in d:

            d[i] = 1

        else:

            d[i] +=1

    for i in d:        #traversing through dictionary to find whose value is more than x.

        if d[i] > x:

            print(i)

arr = [1,3,3,2,2,5,2,3]

k = 4

findSol(arr, k)           

You can also try this code with Online Python Compiler

Run Code

Output:  

3
2

You can also try this code with Online Python Compiler

Run Code

The time complexity of the solution for this problem is O(n) as we need to traverse through the array at once. Here n is the number of the elements in an array.

We can also use the built-in Counter() method instead of the dictionary; For this, you can refer to the GFG article link. You can also use the given link to get the same code in other languages.

Also see,  Rabin Karp Algorithm