Chinese Remainder Theorem

Problem

Given remainders and pairwise coprime moduli, return the smallest non-negative integer x with x mod m[i] equal to remainders[i] for every i, assuming a solution exists.

Build the answer incrementally: keep a current x and a step equal to the product of the moduli processed so far, then advance x by step until it satisfies the next congruence. Return 0 when the lists are empty.

Hint

Adding the product of the already-satisfied moduli preserves all previous congruences.

Test cases

case 1

in: [[2,3,2],[3,5,7]]

expected: 23

case 2

in: [[0,0],[2,3]]

expected: 0

case 3

in: [[1],[5]]

expected: 1

case 4

in: [[1,2,3],[2,3,5]]

expected: 23

case 5

in: [[4,5],[5,7]]

expected: 19

Starter codePython

def chinese_remainder(remainders, moduli):
    # Your code here
    pass

5 test cases · run your code against them in the editor