This post is completed by 1 user

  • 0
 Add to List
Hard

84. Elements in an Array Occurring More Than N/K Times

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

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:
4 appears more than n/ 4 times, Actual count is 5
3 appears more than n/ 4 times, Actual count is 4

Approach:

Naive Approach: Take nested 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 that will store an element and its count.

class

 Elements{
   int element;
   int count;
   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.
  • Navigate all the elements of the given array.
  • Check if an element exists in etms[] if not, insert it with the count 1 and if exists 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 a row gets full, it gets deleted and the size of the Tetris is reduced by 1) see the picture below.
  • Once all the elements of the array are over, check every element of etms[] with the array and print those elements that have N/K times.
Find All Elements in an Array which appears more than NbyK times
 

Output:

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

Related Problems: