How to find the odd element (generalized version) in the list?

Revision en1, by -synx-, 2017-12-01 07:02:08

Given a list of n numbers in which all but one repeat exactly k times, but the remaining one appears less than k times (and at least once).
Find this number (which repeats less than k times).
Expected Complexity
Time  ≤ O(nlgk)
Memory  ≤ O(lgk)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English -synx- 2017-12-01 07:02:08 330 Initial revision (published)