“Given an array of **N integers**, and an integer **K**. Write a program to find all the elements in an array that appear more than n/k times.”

**Examples:**

Example 1:Input:N = 8, K=4, array[] = {3,1,2,2,1,2,3,3}Output:{2,3}Explanation:The frequency of 2 in array appears more than n/k times i.e. (8/4=2) so we will print it, and 3 also has occurred 3 time which is more than 2 (n/k) times.Example 2:Input:N = 5 ,K=2, array[]={1,2,3,4,5}Output:nullExplanation:Here n/k is (5/2=2 in integers) and there are not any integers present whose frequency is not more than 2 , so we will return null.

**NOTE- **The element should be more than n/k elements, not more than equals to.

**Solution**

** Disclaimer**:

*Don’t jump directly to the solution, try it out yourself first.*

**Solution 1: **

**Intuition:**

Here the position of elements is not required so what we can do that we can put all the same elements together which means we can sort it.

**Approach:**

First sort the elements then count the frequency of distinct elements by checking its adjacent elements are equal or not if the frequency of elements is greater than n/k then, print the array element.

**Code:**

## C++ Code

```
#include <bits/stdc++.h>
using namespace std;
void solution(int arr[], int n, int k) {
sort(arr, arr + n);
// Traverse the array
for (int i = 0; i < n;) {
int cnt = 1;
while ((i + 1) < n &&
arr[i] == arr[i + 1]) {
cnt++;
i++;
}
if (cnt > (n / k)) {
cout << arr[i] << " ";
}
i++;
}
}
int main() {
// your code goes here
int n=8, k=4;
int arr[]={3,1,2,2,1,2,3,3};
solution(arr, n, k);
return 0;
}
```

**Output:** 2 3

**Time Complexity: O(n*logn), **as we are sorting the array.

**Space Complexity:-** **O(1)**

## Java Code

```
import java.util.*;
class TUF{
static void solution(int arr[], int n, int k) {
Arrays.sort(arr);
// Traverse the array
for (int i = 0; i < n;) {
int cnt = 1;
while ((i + 1) < n && arr[i] == arr[i + 1]) {
cnt++;
i++;
}
if (cnt > (n / k)) {
System.out.print(arr[i]+" ");
}
i++;
}
}
public static void main(String args[]) {
// your code goes here
int n=8, k=4;
int arr[]={3,1,2,2,1,2,3,3};
solution(arr, n, k);
}
}
```

**Output:** 2 3

**Time Complexity: O(n*logn), **as we are sorting the array.

**Space Complexity:-** **O(1)**

**Solution 2: Using Maps**

**Intuition :**

What we really need is to store the frequency of each element in some data structure and then compare it with n/k.

**Approach**:

Take an unordered map and traverse through the array and keep incrementing the value in the map every time that key appears in the array. At last, compare it with a variable comp which stores the value of n/k. And keep storing the answer in a dynamic array or directly printing it.

**Code:**

## C++ Code

```
#include <bits/stdc++.h>
using namespace std;
void solution(int arr[], int n, int k) {
int comp = n / k;
unordered_map < int, int > mp;
for (int i = 0; i < n; i++) {
mp[arr[i]]++;
}
for (auto x: mp) {
if (x.second > comp)
cout << x.first << " ";
}
}
int main() {
// your code goes here
int n=8, k=4;
int arr[]={3,1,2,2,1,2,3,3};
solution(arr, n, k);
}
```

**Output: **2 3

**Time Complexity: **

**O(n)- **as we are traversing through the array only once.

**Space Complexity:**

**O(n)- **if all the elements are unique in the array so every element will take space.

## Java Code

```
import java.util.*;
class TUF{
static void solution(int arr[], int n, int k) {
int comp = n / k;
HashMap<Integer, Integer > map=new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(arr[i], map.getOrDefault(arr[i],0)+1);
}
for(int x:map.keySet()){
if(map.get(x)>comp)
System.out.print(x+" ");
}
}
public static void main(String args[]) {
// your code goes here
int n=8, k=4;
int arr[]={3,1,2,2,1,2,3,3};
solution(arr, n, k);
}
}
```

**Output: **2 3

**Time Complexity: **

**O(n)- **as we are traversing through the array only once.

**Space Complexity:**

**O(n)- **if all the elements are unique in the array so every element will take space.

Special thanks toplease check out this articleAyush Pandeyfor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,