Hacker News Reader

Comment by shever73 | Hacker News Reader

Yep, that's pretty much how I solved it too. I had (and still have) no idea how to apply the Chinese Remainder Theorem. Looking back at my solution, I just iterated through the input, which I'd mapped to a Python list.

View on HN

Nitpick: there’s no way to apply the Chinese Remainder Theorem. It merely states that “if one knows the remainders of the Euclidean division of an integer n by several integers, then one can* determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.”* (https://en.wikipedia.org/wiki/Chinese_remainder_theorem) It doesn’t say how to determine that number.

https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Comp... describes a few algorithms for doing that.

Well, you can apply the theorem to the problem. Or apply its principles to the problem.

No, you can’t. It only says the problem has a unique solution. It doesn’t even say an efficient algorithm for computing it exists, or even whether an algorithm exists. Neither of those are very hard to prove, but the theorem won’t help you there.

For comparison, let’s say the “sorting theorem” says “if you have n different numbers, you can place them in a sequence so that no number is larger than its predecessor”.

Now, you have two numbers. How do you apply that theorem to place them in a sequence so that no number is larger than its predecessor?

Reply on news.ycombinator.com