Boyer–Moore Majority Vote

Summary No one is supposed to invent the Boyer–Moore voting algorithm during the interview. The point is how to write bug-free codes and make interviewers happy. The order of the branches are quite tricky here. Please remember to increase cnt first, then check if cnt==0, and finally decrease cnt. Several good points here to mention,…

Modular Multiplicative Inverse Concepts

Summary Given a modular MOD, if we want to calculate the division of two integers, we could use the technique Modular Multiplicative Inverse. To calculate b_, we could use Fermat’s little theorem. If mod is a prime number, we have If we use Binary Exponentiation technique, we could calculate b_ efficiently.

Subarray & DP

Summary In this post, I will introduce some problems related to subarray and dynamic programming. The most important thing in subarray is that it is continuous. So usually one dimension of the DP will be chosen as “a subarray starting at index i”. Then we need a separate loop for it to choose the best…