Chinese Remainder Theorem
Learn about the Chinese Remainder theorem that is very useful in solving coding interview problems.
We'll cover the following...
Problem introduction
The Chinese Remainder theorem is used to solve problems typical of the form “Find a number which when divided by 2 leaves remainder 1, when divided by 3 leaves remainder 2, and when divided by 7 leaves remainder 5”. These problems can be reformulated into a system of linear congruence and can then be solved using the Chinese Remainder theorem. For example, the above problem can be expressed as a system of three linear congruences:
x ≡ 1 (mod 2), x ≡ 2 mod(3), x ≡ 5 mod (7)
We are given with two arrays, i.e., num[] and rem[]. For the above example, we can have num[] = {2, 3, 7} and rem[] = {1, 2, 5}.
The Chinese Remainder theorem states that there always exists an x that satisfies given congruence.
Basically, we are given k numbers which are pairwise co-prime and given remainders of these numbers when an unknown number x is ...