please give the proof of moore voting algorithm in general .please do not give it by testcases.i want to understand why in general it works?
Proof of algorithm issue
@Rj.25 understand with a diagram
if a number occurs more than n/2 times then all other will try to cancel it out but if all other no are less than n/2 than they won’t.
i hope its clear if yes dont forget to hit like and mark resolved
actually i do not understand that the voter in the moore algorithm changed can be changed nultiple times during traversal how we can ensure that the final voter we are getting is the majority element if the majority element exists.why it can not be that some other voter which was previously replaced can be the majority element?
@Rj.25 if total no are 10 and something like this 2222111111 2 is starting majority but as you can see 1 occurs 6 times >n/2 elements so final cnt will be 2 and that of 1 as all the 2 cancels 1 and cnt of 1 starts inc. see the image above if a element is majority than all others cant cancel it out completely
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.