Efficiency of the script (finding a pair of integers which have the same remainder)

Solution 1:

Note that your function doesn't have the parameters described by the problem -- it should take n and A as parameters, not take an m and generate its own A.

The problem is much easier if you look at it as simply "find a pair of numbers with the same value mod n". An simple approach to this is to bucket all of the numbers according to their value % n, and return a bucket once it has two numbers in it. That way you don't need to compare each pair of values individually to see if they match.

>>> import random
>>> def find_equal_pair_mod_n(n, A):
...     assert len(A) > n
...     mods = {}
...     for i in A:
...         xy = mods.setdefault(i % n, [])
...         xy.append(i)
...         if len(xy) > 1:
...             return tuple(xy)
...
>>> find_equal_pair_mod_n(10, [random.randint(0, 34) for _ in range(12)])
(26, 6)
>>> find_equal_pair_mod_n(10, [random.randint(0, 34) for _ in range(12)])
(30, 10)
>>> find_equal_pair_mod_n(10, [random.randint(0, 34) for _ in range(12)])
(32, 32)
>>> find_equal_pair_mod_n(10, [random.randint(0, 34) for _ in range(12)])
(1, 1)
>>> find_equal_pair_mod_n(10, [random.randint(0, 34) for _ in range(12)])
(28, 8)