Given an array of length N+K-1 consisting of only the first N odd numbers. Each number occurs exactly once, except for one number, which occurs K times in the array. Given S - the sum of the numbers in the array, determine the repeated element.
Let the repeated number be X.
Reorder the elements of the array to
where the K-1 repeated X are placed at the end.
The sum of the first N terms is N^2 (see this for proof) and the remaining K-1 terms is (K-1)*X. The total sum is therefore:
which is the answer we seek!
O(1) per test case.
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)