3 ms·
Very short, expressed in number of items in the lists. Once N is large enough, these two single-item lists have that: First list: (N) Second list: (N + 1) N
by Someone 5y ago
Very short, expressed in number of items in the lists. Once N is large enough, these two single-item lists have that:
First list: (N)
Second list: (N + 1)
N = 10^10^15 is large enough for that.
I think you can construct much smaller examples by looking at Pythagorean triples. Since 3² + 4² = 5² and 5² + 12² = 13², the lists (9k, 16k, 169k) and (25k, 144k, 25k) have the same sum of square roots (22√k) for all k. Subtract one from one of the numbers, and you’ll have a close match, say with error e.
Do the same for a second pair of Pythagorean triples, giving you an error of f. Compute a good rational approximation p/q of e/f, and linearly combine the pairs of sets to get any arbitrary small difference (edit: that construction works starting with any two sets of two sets of numbers)
And I don’t think there is an “in practice” for this problem. When do you ever have to make this computation? If ever, does it matter if your code fails on a tiny fraction of all inputs?