2
$\begingroup$

Note that "most frequent" here means "any of the most frequent, don't care which".
Example $n=3$. Consider the Bell partitions
aaa
aab
aba
baa
abc
which subsume all possibilities of a 3 element array A (different letters are different values). You just need one question: Are the last two elements equal? If yes, return the last of the array. If no, return the first.
If logical combinations (like "is there at least one = between the last four elements?") are allowed, I'd expect, of course, $<log_2(B_n)$ questions, where $B_n$ is the corresponding Bell number. The tricky part is that you may return the array number most convenient for your algorithm, and as the example shows, less than the above upper bound will suffice. (Two for $n=4$, at most five for $n=5$. Also note that the actual number of IF statements possibly will be higher as two independent questions with four possible answers need three IF, and "five" refers to my actual IF...ELSE IF... construct, but for explicite algorithm details, I pester StackOverflow :-) I'd be happy with a sharper bound at the moment.)

Improve this question
$\endgroup$
12
  • 3
    $\begingroup$ What kind of queries do you allow? (With no restrictions, one can trivially find the answer using a single $n$-valued query, or $\log_2 n$ binary queries.) $\endgroup$
    – Emil Jeřábek
    Commented Dec 5, 2017 at 12:58
  • $\begingroup$ Maybe this answers your question? Boyer-Moore majority vote algorithm $\endgroup$
    – Jay Pantone
    Commented Dec 5, 2017 at 17:32
  • $\begingroup$ Seems like a good question for CodeGolf.SE :-) $\endgroup$
    – Nate Eldredge
    Commented Dec 5, 2017 at 22:53
  • 1
    $\begingroup$ I still don’t quite understand what you are saying. If you formally allow arbitrary queries, but regardless of that count the number of equality queries that are needed to implement them, how is that any different from just only allowing equality queries? Anyway, it is easy to show that in that case, any algorithm needs at least $\binom{n-1}2$ equality queries in the worst case, hence you basically cannot beat the trivial $\binom n2$ algorithm that compares everybody to everybody. $\endgroup$
    – Emil Jeřábek
    Commented Dec 6, 2017 at 13:24
  • 1
    $\begingroup$ @Hauke: In the question you write that "Two for n=4", but in your first comment you write that the "factual costs are 3" [in the n=4 case] - so it would be nice to state your problem more explicitly. $\endgroup$
    – domotorp
    Commented Dec 6, 2017 at 20:42

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .