2
$\begingroup$

I have an array of 64-bit integers of length $n$ and I want to find the frequency of each element in $\mathcal{O}(n)$? is that possible?

my idea was to use a hashmap but it seems to me that the adversary would always be able to find a pathological case.

Improve this question
$\endgroup$
7
  • $\begingroup$ Yes, you can use HashMap. adversary would always be able to find a pathological case: you can use your own hash function: $h(x) = p \cdot x \pmod {m}$, where $p$ and $m$ are (large) prime numbers randomly selected at the beginning of the program. While adversarial inputs exist (e.g. $0$, $m$, $2m$, ...), the adversary doesn't know them, since they don't know $p$ and $m$. $\endgroup$
    – user114966
    Sep 4, 2020 at 23:35
  • 2
    $\begingroup$ Since they are integers of fixed length, you can sort them in $O(n)$ and then count their repetitions in one pass. $\endgroup$
    – plop
    Sep 5, 2020 at 1:51
  • 1
    $\begingroup$ Use radix sort with an "alphabet" of size 256, say. $\endgroup$
    – Yuval Filmus
    Sep 5, 2020 at 5:52
  • $\begingroup$ Is there a limit on the $n$? $\endgroup$
    – kelalaka
    Sep 5, 2020 at 7:11
  • $\begingroup$ Since the integers are all upper bounded by an absolute constant the "counting" part of counting sort already solves the problem in $O(n)$ time. $\endgroup$
    – Steven
    Sep 5, 2020 at 12:50

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.