Chinese Remainder Theorem
HardMathNumber TheoryArray
Description
Given two arrays r and m of equal length, return the smallest non-negative integer x such that x ≡ r[i] (mod m[i]) for all i. Return -1 if the system has no solution. The moduli may share factors.
Examples
Input:
r = [2,3,2], m = [3,5,7]Output:
23Explanation:
The unique solution x = 23 satisfies all three congruences modulo lcm(3,5,7) = 105.
Input:
r = [0,0], m = [3,5]Output:
0Explanation:
x = 0 satisfies both 0 mod 3 = 0 and 0 mod 5 = 0, so the smallest non-negative solution is 0.
Input:
r = [1,2], m = [2,4]Output:
-1Explanation:
The residues 1 mod 2 and 2 mod 4 are inconsistent because mod 2 they disagree, so the answer is -1.
Constraints
- •
1 ≤ r.length = m.length ≤ 20 - •
1 ≤ m[i] ≤ 10⁹