title: Find All Elements in an Array which appears more than N/K times, N is Array Size and k is a Number
body: <p>Every where best algorithm given is this </p>
  
  <p>1) Create a temporary array of size (k-1) to store elements and their counts (The output elements are going to be among these k-1 elements). Following is structure of temporary array elements.</p>
  
  <p>2) Traverse through the input array and update temp[] (add/remove an element or increase/decrease count) for every traversed element. The array temp[] stores potential (k-1) candidates at every step. This step takes O(nk) time.</p>
  
  <p>3) Iterate through final (k-1) potential candidates (stored in temp[]). or every element, check if it actually has count more than n/k. This step takes O(nk) time.</p>
  
  <p>Resources i referred are :-</p>
  
  <p>1) <a href="http://www.geeksforgeeks.org/given-an-array-of-of-size-n-finds-all-the-elements-that-appear-more-than-nk-times/" rel="nofollow">http://www.geeksforgeeks.org/given-an-array-of-of-size-n-finds-all-the-elements-that-appear-more-than-nk-times/</a> </p>
  
  <p>2) <a href="http://algorithms.tutorialhorizon.com/find-all-elements-in-an-array-which-appears-more-than-nk-times-n-is-array-size-and-k-is-a-number/" rel="nofollow">http://algorithms.tutorialhorizon.com/find-all-elements-in-an-array-which-appears-more-than-nk-times-n-is-array-size-and-k-is-a-number/</a></p>
  
  <p>**To me better algorithm looks like below which is O(n) **</p>
  
  <p>1)Start iterating through array.</p>
  
  <p>2)For each element check if element exist in hash map . If yes increase counter otherwise add it with counter 1</p>
  
  <p>3)Also after addition of each element check whether count is greater than n/k times. If yes print</p>
  
  <p>Here memory complexity will be O(N) which is bad than O(K-1) but time complexity is much better here which is O(n) compared to O(nk) in previuos algo.</p>
  
  <p>so is n't second algo better considering time complexity and simplicity/readability or answer is  <code>Depends on</code> kind depending upon where we want to compromise i.e. either on
  time or memory ?</p>