Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given an array of size of N and num­ber k. Find all ele­ments in an Array which appears more than N/K times.

Input: Array [] and num­ber k.

Exam­ple:

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 ele­ment with all other ele­ments, Time Com­plex­ity -   O(n2) time.

Bet­ter Approach: Tetris Game tech­nique– O(Nk)

  • We will cre­ate a class struc­ture which will store an ele­ment and its count.
class Elements{
   intelement;
   intcount;
   public Elements(int element, int count){
   this.element = element;
   this.count =count;
  }
}
  • Cre­ate array etms[] con­tains k-1 objects of class Ele­ments with ele­ment =0 and count = 0.
  • So idea is, nav­i­gate all the ele­ments of given array.
  • Check if ele­ment 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 insert­ing an ele­ment, if it is not, fol­low the pre­vi­ous step. If it is full then reduce the count of every exist­ing ele­ment 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 pic­ture below.
  • Once all the ele­ments of array gets over, check every ele­ment of etms[] with array and print those ele­ments which has N/K times.
Find All Elements in an Array which appears more than NbyK times

Find All Ele­ments in an Array which appears more than NbyK times

Com­plete Code:


Out­put:

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

You may also like...

  • cab­hishek

    Why not use hashmap to store the count ?

    • tuto­ri­al­hori­zon

      You can use the Hashmap , if you are stor­ing all the ele­ments in hashmap then it will take O(n) space. you can apply the same logic which is men­tioned in the post with hash map size k-1, then space com­plex­ity will be O(k-1)

  • Amar­nath

    Good logic.
    I have a ques­tion, 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 ele­ments and the ele­ments which are hav­ing >= N/K = 14/4 = 3 will be the result. Here the count of ele­ment 4 is hav­ing count >= 3. Hence this should be the answer. But why is 3 also part of the result? Since ele­ment 3 has count only 2, it should not be added in the result right?