"""

Chinese Remainder Theorem

Solves a system of simultaneous congruences using the Chinese Remainder

Theorem. Given pairwise coprime moduli, finds the smallest positive integer

satisfying all congruences.

Reference: https://en.wikipedia.org/wiki/Chinese_remainder_theorem

Complexity:

Time: O(n * m) where n is the number of equations and m is the solution

Space: O(1)

"""

from __future__ import annotations

from algorithms.math.gcd import gcd

def solve_chinese_remainder(nums: list[int], rems: list[int]) -> int:

"""Find the smallest x satisfying x % nums[i] == rems[i] for all i.

Args:

nums: List of pairwise coprime moduli, each greater than 1.

rems: List of remainders corresponding to each modulus.

Returns:

The smallest positive integer satisfying all congruences.

Raises:

Exception: If inputs are invalid or moduli are not pairwise coprime.

Examples:

>>> solve_chinese_remainder([3, 7, 10], [2, 3, 3])

143

"""

if not len(nums) == len(rems):

raise Exception("nums and rems should have equal length")

if not len(nums) > 0:

raise Exception("Lists nums and rems need to contain at least one element")

for num in nums:

if not num > 1:

raise Exception("All numbers in nums needs to be > 1")

if not _check_coprime(nums):

raise Exception("All pairs of numbers in nums are not coprime")

k = len(nums)

x = 1

while True:

i = 0

while i < k:

if x % nums[i] != rems[i]:

break

i += 1

if i == k:

return x

x += 1

def _check_coprime(list_to_check: list[int]) -> bool:

"""Check whether all pairs of numbers in the list are coprime.

Args:

list_to_check: List of integers to check for pairwise coprimality.

Returns:

True if all pairs are coprime, False otherwise.

"""

for ind, num in enumerate(list_to_check):

for num2 in list_to_check[ind + 1 :]:

if gcd(num, num2) != 1:

return False

return True