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.

$\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$ 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

Your Answer

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

Browse other questions tagged or ask your own question.