Input: two lists of numbers.

Objective: find the smallest difference between them (this is, the minimum value
that `mod(listA[i] - listB[j])`

can take).

There are two simple ways to solve this problem and I will explain them here.
From now on, `m`

is the size of `listA`

and `n`

is the size of `listB`

.

The first one, and also the one that is easier to implement and to debug is to
simply compare each element from `listA`

to each element from `listB`

. This,
however simple, has O(m n) running time.

The second way to solve this problem, slightly more complicated, is to sort both
lists and iterate through them, advancing the iterator that points to the
smallest element (so that after an iteration the difference between the values
**may** be smaller). Modern programming languages tend to have quite good
implementations of at least one O(n lg n) sorting algorithm, so you are likely
not going to have to (re)write quicksort.

The sorting step has time complexity of O(m lg m) + O(n lg n) and the iteration’s
worst-case time complexity is O(m + n). Making this substantially faster for
large enough `m`

and `n`

.

Here is a simple implementation of the second approach described above using C++ that I just finished.

```
unsigned find_smallest_difference(const uvector& a, const uvector& b) {
uvector::const_iterator it_a = a.begin();
uvector::const_iterator it_b = b.begin();
unsigned diff;
unsigned smallest_difference = UINT_MAX;
while (it_a != a.end() && it_b != b.end()) {
diff = *it_a >= *it_b ? (*it_a - *it_b) : (*it_b - *it_a);
if (diff < smallest_difference) {
smallest_difference = diff;
}
// Increment the iterator that points to the smallest element.
if (*it_a < *it_b) {
++it_a;
}
else if (*it_a > *it_b) {
++it_b;
}
else { // Found difference == 0, it is okay to break the loop.
break;
}
}
return smallest_difference;
}
```