PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Misha Chorniy
Editorialist: Animesh Fatehpuria
PROBLEM
There is a hidden sorted array of length N. Each number in the array appears exactly K times, except one element, which appears at least once, but less than K times. The task is to identify that element.
You’re given N but not K. You are allowed to ask the judge the following query: What is the value of the element at index i of the array? Identify the value of the element with frequency less than K by asking at most 60 such queries.
Constraint: 3 \le N \le 10^5.
EXPLANATION
First, we note that the amount of allowed queries is roughly 3 * \log(N). We’ll divide the solution into
two steps which collectively take 3 * \left\lceil{\log{N}}\right \rceil steps in the worst case.
Finding the value of K
This can be done using one binary search. Since we know that A is sorted, we can find the frequency of
A_1 with one binary search by finding the last occurrence of A_1 in A. This takes \left\lceil{\log{N}}\right \rceil queries. Let X denote the frequency of A_1.
From the problem statement, we can be sure that either K = X or A_1 is the odd element. We need to find out which one of the two cases it is. To do that, we can utilize O(1) more queries to compute the frequency of A_{X + 1}. This is quite simple to do so I’ll leave it as an exercise.
Solving for the odd element
Now we have K, and we have at least 2 \cdot \left\lceil{\log{N}}\right \rceil queries to spare. We present a solution that uses binary search (yet again!) to solve for the odd element. Consider maximal groups of equal values in our hidden array A. There are exactly \left\lceil{\frac{N}{K}}\right \rceil groups. Let’s call them G_1, G_2, \cdots, G_{\left\lceil{\frac{N}{K}}\right \rceil}. The problem we’re trying to solve is equivalent to finding the odd sized group i.e. the only group fo size less than K.
To do this, we can do a binary search on “groups”. We’ll assume every group is of size K (for now). Suppose we’re looking at the middle group, with index j. Look at the last element of G_{j} (which is A_{j * K}) and the first element of G_{j + 1} (which is A_{j * K + 1}). What can we say if these two quantities are equal? It means that there
exists a group of size < K to the left of group j, so we can recurse on that half. Similarly, if these two values
are unequal, we are sure that all groups upto group j have size K, so the answer lies in the right half.
Since on each step we make two queries, overall this procedure makes 2 \cdot \left\lceil{\log{N}}\right \rceil queries
which is within our limit.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.