# Find All Elements in an Array which appears more than N/K times, N is Array Size and k is a Number.

Objective: Given an array of size of N and number k. Find all elements in an Array which appears more than N/K times.

Input: Array [] and number k.

Example:

```int[] arrA = { 2, 2, 4, 4, 3, 5, 3, 4, 4, 6, 4, 3, 3, 8 };

K = 4

N/k = 14/4 = 3

Output will be [3,4] they appear 5, 4 times respectively.
```

Approach:

Naive Approach: Take two for loops , check every element with all other elements, Time Complexity –   O(n2) time.

Better Approach: Tetris Game technique- O(Nk)

• We will create a class structure which will store an element and its count.
```class Elements{
intelement;
intcount;
public Elements(int element, int count){
this.element = element;
this.count =count;
}
}
```
• Create array etms[] contains k-1 objects of class Elements with element =0 and count = 0.
• So idea is, navigate all the elements of given array.
• Check if element exist in etms[] if not, insert it with the count 1 and if exist then increase its count.
• Also check if etms[] gets full when inserting an element, if it is not, follow the previous step. If it is full then reduce the count of every existing element in the etms[]. (Just think of a Tetris game, when row gets full, it gets deleted and size of the Tetris reduced by 1) see the picture below.
• Once all the elements of array gets over, check every element of etms[] with array and print those elements which has N/K times.

Complete Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 //Objective is to find the element in an array ///which occurs more than n/k times public class NbyKTimes { public void findElement(int[] arrA, int k) { Elements[] emts = new Elements[k – 1]; for (int j = 0; j < emts.length; j++) { emts[j] = new Elements(0, 0); } for (int i = 0; i < arrA.length; i++) { int index = found(emts, arrA[i]); if (index >= 0) { // means element found in Elements array // just increase its count emts[index].count++; } else { addtoArray(emts, arrA[i]); } }// // now check if any of the elements in the Elements array appears // more than n/k times for (int i = 0; i < emts.length; i++) { int cnt = 0; for (int j = 0; j < arrA.length; j++) { if (arrA[j] == emts[i].element) { cnt++; } } if (cnt > (arrA.length / k)) { System.out.println(emts[i].element + " appears more than n/" + k + " times, Actual count is " + cnt); } } } public void addtoArray(Elements[] emts, int x) { // check is array is full or not for (int j = 0; j < emts.length; j++) { if (emts[j].count == 0) {// find the empty place and add it emts[j].element = x; return; } } // if we have reached here means array is full // reduce the counter of every element for (int j = 0; j < emts.length; j++) { emts[j].count—; } } // This found function will check whether element already exist or not // if yes then return its index else return -1 public int found(Elements[] emts, int x) { for (int j = 0; j < emts.length; j++) { if (emts[j].element == x) { return j; } } return –1; } public static void main(String args[]) { int[] arrA = { 2, 2, 4, 4, 3, 5, 3, 4, 4, 6, 4, 3, 3, 8 }; NbyKTimes n = new NbyKTimes(); n.findElement(arrA, 4); } } class Elements { int element; int count; public Elements(int element, int count) { this.element = element; this.count = count; } }

view raw

NbyKTimes.java

hosted with ❤ by GitHub

Output:

```4 appears more than n/4 times, Actual count is 5
3 appears more than n/4 times, Actual count is 4
```

### 7 thoughts on “Find All Elements in an Array which appears more than N/K times, N is Array Size and k is a Number.”

1. Why not use hashmap to store the count ?

• You can use the Hashmap , if you are storing all the elements in hashmap then it will take O(n) space. you can apply the same logic which is mentioned in the post with hash map size k-1, then space complexity will be O(k-1)

2. Good logic.
I have a question, in the above chart’s last step 8 has 1, 4 has 3, 3 has 2. As per logic we will look at the count of all the elements and the elements which are having >= N/K = 14/4 = 3 will be the result. Here the count of element 4 is having count >= 3. Hence this should be the answer. But why is 3 also part of the result? Since element 3 has count only 2, it should not be added in the result right?

3. Thank you so much for the diagram !! It made understanding this algo a lot easier 🙂
Also, the code is very clean.

4. how do you optimise if the array is sorted?