Could anybody help with proving this phrase from the Solution Approach: "It is im


#1

Could anybody help with proving this phrase from the Solution Approach:
“It is important to note that if at a given time, you have 3 distinct element from the array, if you remove them from the array, your answer does not change.”


#2

Let call the return result is x (x will appear more than n/3), if x does not belong to that 3 distinct elements, if you remove those 3 distinct element, the number of time of x appears in the array still more than (n-3)/3 -> the result never change. If x is one of the 3 distinct elements, removing these 3 distinct elements still make x appear more than (n-3)/3 = n/3 - 1.


#3

That statement is not true.
Counterexample is [1 2 3 1 5]. First three elements are distinct in this array, but removing them gives array of [1 5] with different answer (1 or 5 instead of just 1).
Good statement would be “… answer is still be among answers for the new array”.


#4

These are only the candidates, after that you would check if the count of each of them really exceed n/3 . Think in this way even if the array does not have any repeat number it would return two numbers and you have two check those.