Hidden Single (Version 1)

The nasty part is that the query only answers existence, not count. So the obvious “count each value” plan is dead on arrival. The trick is to stop asking for exact counts and instead use a parity-ish contradiction: pretend the singleton also appeared twice.

State

We solve recursively on an interval of positions $[l,r]$ that is guaranteed to contain the singleton position.

For this interval, maintain two lists:

• vals: values whose all occurrences are inside $[l,r]$.
• waste: values that have exactly one occurrence inside $[l,r]$ and another occurrence outside it.

At the start, $[l,r]=[1,2n-1]$, every value is fully inside, so:

$$vals = \{1,2,\dots,n\}, \qquad waste = \varnothing.$$

The singleton value is always inside vals, because its only occurrence is inside the interval we recurse into.

Splitting an interval

Let

$$mid = \left\lfloor \frac{l+r}{2} \right\rfloor.$$

We split into:

$$L=[l,mid], \qquad R=[mid+1,r].$$

Now classify every relevant value for the two children.

For a value in waste, we know it appears exactly once in the current interval. So one query on the left half is enough:

• if it appears in $L$, it becomes waste for $L$;
• otherwise it becomes waste for $R$.

For a value in vals, all its occurrences are inside the current interval. Query the left half:

• if it does not appear in $L$, then all its occurrences are in $R$, so it goes to vals of $R$;
• if it appears in $L$, query $R$ too:
  • if it appears in both halves, it is crossing, so it goes to waste of both children;
  • if it appears only in $L$, it goes to vals of $L$.

That is at most $2$ queries for a vals value and $1$ query for a waste value.

How do we know which half contains the answer?

For a child interval $I$, suppose we have built its lists childVals and childWaste.

If every value appeared twice, then:

• each value in childVals would contribute $2$ positions inside $I$;
• each value in childWaste would contribute $1$ position inside $I$.

So the predicted length is:

$$pred(I)=2\cdot |childVals|+|childWaste|.$$

The real length is just:

$$len(I)=R_I-L_I+1.$$

If $I$ does not contain the singleton, then all values behave normally, and:

$$pred(I)=len(I).$$

If $I$ does contain the singleton, then the singleton value is in childVals, but it contributes only $1$ real position, while our fake count adds $2$. So:

$$pred(I)=len(I)+1.$$

That is the whole damn problem. The wrong-length half is the half containing the singleton. Recurse there.

Stopping

If vals has size $1$, that one value must be the singleton. Why? The true singleton is always in vals, and there is only one candidate left. No drama.

Query bound

For an interval of length $m$, the invariant gives:

$$m = 2\cdot |vals| + |waste| - 1,$$

because every value in vals contributes $2$ positions except the singleton, which contributes $1$, and every value in waste contributes $1$.

In one recursive step, the number of queries is at most:

$$2\cdot |vals| + |waste| = m+1.$$

The visited interval lengths shrink by halves, starting from $2n-1$. Their total is below about $4n$, and there are only $O(\log n)$ recursive levels. More precisely, this fits inside the required

$$4n + 2\lceil \log_2 n \rceil$$

queries.

So the strategy is deterministic, clean, and query-limit friendly. No gambling, no “hope the judge is chill” nonsense.