Find if there is an element repeating itself n/k times

Question

You have an array size n and a constant k (whatever)

You can assume the the array is of int type (although it could be of any type)

Describe an algorithm that finds if there is an element(s) that repeats itself at least n/k times... if there is return one. Do so in linear time (O(n))

The catch: do this algorithm (or even pseudo-code) using constant memory and running over the array only twice

Answer 1

A simple O(n) algorithm would be to keep a hashed map from the number found to the number of instances found. Using a hashed map is important for maintaining O(n). The, a final pass over the map will reveal the answers. This pass is also O(n) since the worst case scenario is that every element appeared only once and hence the map is the same size as the original array.

Answer 2

I don't know if you are restricted on which additional data structures you can use.

What about creating a hashmap with 'elements' <--> count mapping. Insertion is O(log N). Lookup is O(1). For each element, lookup on hashtable, insert if does not exist with count 1. If exists, check if count < (n/k). It will stay O(n).

EDIT:

I forgot the constant memory restriction. It's preallocating hash map entries with N elements permitted?

Answer 3

thanks for the quick respond... I knew it will raise more question so let me give some example for instance

41 25 347 352 24 57 24 -12 64 32 25 43 12 41 25 - is our array k lets say is 5 what leads to 15/5=3 we have number "25" so 25 should be returned

another one -3 23 12 64 23 12 12 -3 23 = array.length =9 k=3 so 9/3=3 23/12 should be returned.

"So what have you tried and what specifically are you having trouble with? – Chris Dunaway" trouble will lets say that we all know how to make it in o(n) but how to make it by running over the array only twice :(

"By "repeat itself," do you mean it should be a consecutive run of the same number?" same number :) see examples above please.

"Constant memory per array, or constant memory per element?" dont understand the question :( sorry

"Sorry, I read the "constant memory" requirement as being a "bonus marks" question... :-) " as a matter of fact it's a bonus question the memory requirement.