# How do you find all integers in a sorted array of size n that appear n/k times?

I try to find the solution to this problem: How do you find all integers in a sorted array of size n that appear n/k times in less than O(klogn) time?

I could only find this question, where O(klogn) solution was provided.

Let's start with the case $$k = 2$$, and assume that the algorithm is comparison-based.
I claim that any algorithm that finds even a single element appearing $$n/2$$ times must know an index $$i$$ such that $$A[i+1] = A[i+n/2]$$. Indeed, suppose that this is not the case, and let us assume for simplicity that the entries of $$A$$ are real numbers. Let us say that the algorithm known the following values: $$A[i_1] = \cdots = A[j_1] < A[i_2] =\cdots = A[j_2] < \cdots$$ It is consistent with the algorithm's knowledge that $$A[i_1-1] < A[i_1] < A[j_1+1]$$ and so on, and with a little effort we can arrange that there is no element appearing $$n/2$$ times.
Consider now the $$n/2+1$$ arrays of the following form: there is a run of $$n/2$$ many $$0$$s starting at some position $$j \in \{1,\ldots,n/2+1\}$$, and the rest of the elements are unique. In each such array, there is a unique choice for the index $$i$$ mentioned above. Thus the decision tree representing the algorithm has at least $$n/2+1$$ leaves, and so it must have depth $$\Omega(\log n)$$.
In the general case, the algorithm should know an index $$i$$ such that $$A[i+1] = A[i+n/k]$$ for each element which is output. We can partition the array into $$k/2$$ parts of size $$2n/k$$, and consider $$(n/k+1)^k$$ examples as before, where the $$r$$th element appearing $$n/k$$ times is in the $$r$$th part. This gives a lower bound of $$\Omega(k\log(n/k))$$, matching your upper bound for nearly all values of $$k$$.