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

by

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.
Find All Elements in an Array which appears more than NbyK times
Find All Elements in an Array which appears more than NbyK 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;
}
}

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

Related Posts: