**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(n^{2}) time.

**Better Approach: Tetris Game technique- O(Nk)**

- We will create a class structure which will store an element and its count.

classElements{intelement;intcount;publicElements(intelement,intcount){this.element = element;this.count =count; } }

- Create array
contains k-1 objects of class*etms[]*with element =0 and count = 0.*Elements* - 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:**

//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; | |

} | |

} |

**Output**:

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