Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Solution
2.1.
Approach
2.2.
Code
3.
Frequently Asked Questions
3.1.
How to find elements that appear more than n/k times?
3.2.
How to find elements that appear more than two times?
3.3.
How to create a frequency dictionary of a given array?
3.4.
What is the time complexity of this problem?
3.5.
What is n in the problem "Given an array of size n and a value k, we need to find all the elements that appear more than n/k times?"
4.
Conclusion
Last Updated: Mar 27, 2024

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)           

Output:  

3
2

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

How to find elements that appear more than n/k times?

First, we need to find the length of the array given. Then, we need to calculate the length/k value. Next, we will create a frequency dictionary for the given array. At last, we will traverse through the dictionary and find whose value is more than length/k.

How to find elements that appear more than two times?

First, we need to find the length of the array given. Next, we will create a frequency dictionary for the given array. At last, we will traverse through the dictionary and find whose value is two by using a simple if condition.

How to create a frequency dictionary of a given array?

A frequency dictionary can be easily created by first creating an empty dictionary. Then we need to traverse through the array, and if the array element is not in the dictionary, add it to it with value 1. If present, increase the value by 1. 

What is the time complexity of this problem?

The time complexity of the solution for this problem, "Given an array of size n and a value k, find all elements that appear more than n/k times," is O(n) as we need to traverse through the array at once. Here n is the number of the elements in an array.

What is n in the problem "Given an array of size n and a value k, we need to find all the elements that appear more than n/k times?"

In the problem “Given an array of size n and a number k, find all elements that appear more than n/k times,” the n value is the number of elements of an array given. We can calculate this using the len() python method.

Conclusion

This article extensively discussed the problem "Given an array of size n and a value k, we need to find all the elements that appear more than n/k times." We start with a brief introduction, then discuss the problem with a simple example.

Recommended problems -

 

After reading about this problem, are you not feeling excited to read/explore more articles on similar problems? Don't worry; Coding Ninjas has you covered. Refer to our Guided Path on Coding Ninjas Studio to improve yourself in Competitive ProgrammingData Structures and AlgorithmsJavaScriptSystem Design, and many more! If you want to test your confidence in coding, you may check out the contests and participate in the mock test series hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview bundle, and interview experiences for placement preparations.

Nevertheless, you can consider our paid courses to give your career improvement an edge over others!

Do upvote our blogs and articles if you find them helpful and engaging!

Happy Learning!

 

Previous article
Find the subarray with the least average
Next article
Sort a Rotated Sorted Array
Live masterclass