Dont understand why solution approach works


#1

I looked at the solution approach and implemented it. Still don’t understand why it works though. Needed a better explanation.


#2

Read This forum , It shows an analogy with majority finding problem.[https://apps.topcoder.com/forums/;jsessionid=128D2CE9DB2D4348DC73C0B3BCCC4750?module=RevisionHistory&messageID=1464587]


#3

Lets only consider looking for a number more than n/2 times.
The idea is if we remove one majority element and one minority element the majority element remains the same. How the numbers are removed it by keeping track of a ‘selected number’ initialized by index 0. we compare it to the A[i] for 0<i<n. Every time we see A[selected] == A[i] we increase count of selected number else we decrease the count. Decreasing the count means you have removed A[i] and one copy of the A[selected]. If the count reaches 0, you update the selected = i and keep on doing the process. In the end a check is required to see if A[selected] is really the number which occurs > n/2 times. This can be easily done in one iteration of the array.
Now let’s say we want to see if a number occurs more than n/k times. If we remove k-1 minority elements and 1 majority element the majority element remains the same. K was 2 in our previous case. For this questions k = 3, hence we remove 3 distinct numbers, and at the end check if any of the 2 numbers we kept is occurring more than n/3 or not.