Minimum common remainder of division

Question

I have n pairs of numbers: ( p[1], s[1] ), ( p[2], s[2] ), ... , ( p[n], s[n] )

Where p[i] is integer greater than 1; s[i] is integer : 0 <= s[i] < p[i]

Is there any way to determine minimum positive integer a , such that for each pair :

( s[i] + a ) mod p[i] != 0

Anything better than brute force ?

Answer 1

It is possible to do better than brute force. Brute force would be O(A·n), where A is the minimum valid value for a that we are looking for.

The approach described below uses a min-heap and achieves O(n·log(n) + A·log(n)) time complexity.

First, notice that replacing a with a value of the form (p[i] - s[i]) + k * p[i] leads to a reminder equal to zero in the i^th pair, for any positive integer k. Thus, the numbers of that form are invalid a values (the solution that we are looking for is different from all of them).

The proposed algorithm is an efficient way to generate the numbers of that form (for all i and k), i.e. the invalid values for a, in increasing order. As soon as the current value differs from the previous one by more than 1, it means that there was a valid a in-between.

The pseudocode below details this approach.

1. construct a min-heap from all the following pairs (p[i] - s[i], p[i]), 
    where the heap comparator is based on the first element of the pairs.
2. a0 = -1; maxA = lcm(p[i])
3. Repeat
     3a. Retrieve and remove the root of the heap, (a, p[i]).
     3b. If a - a0 > 1 then the result is a0 + 1. Exit.
     3c. if a is at least maxA, then no solution exists. Exit.
     3d. Insert into the heap the value (a + p[i], p[i]).
     3e. a0 = a

Remark: it is possible for such an a to not exist. If a valid a is not found below LCM(p[1], p[2], ... p[n]), then it is guaranteed that no valid a exists.

---

I'll show below an example of how this algorithm works.

Consider the following (p, s) pairs: { (2, 1), (5, 3) }.

The first pair indicates that a should avoid values like 1, 3, 5, 7, ..., whereas the second pair indicates that we should avoid values like 2, 7, 12, 17, ... .

The min-heap initially contains the first element of each sequence (step 1 of the pseudocode) -- shown in bold below:

• 1, 3, 5, 7, ...

• 2, 7, 12, 17, ...

We retrieve and remove the head of the heap, i.e., the minimum value among the two bold ones, and this is 1. We add into the heap the next element from that sequence, thus the heap now contains the elements 2 and 3:

• 1, 3, 5, 7, ...

• 2, 7, 12, 17, ...

We again retrieve the head of the heap, this time it contains the value 2, and add the next element of that sequence into the heap:

• 1, 3, 5, 7, ...

• 2, 7, 12, 17, ...

The algorithm continues, we will next retrieve value 3, and add 5 into the heap:

• 1, 3, 5, 7, ...

• 2, 7, 12, 17, ...

Finally, now we retrieve value 5. At this point we realize that the value 4 is not among the invalid values for a, thus that is the solution that we are looking for.

Answer 2

I can think of two different solutions. First:

p_max = lcm (p[0],p[1],...,p[n]) - 1;
for a = 0 to p_max:
    zero_found = false;
    for i = 0 to n:
        if ( s[i] + a ) mod p[i] == 0:
            zero_found = true;
            break;
    if !zero_found:
        return a;
return -1;

I suppose this is the one you call "brute force". Notice that p_max represents Least Common Multiple of p[i]s - 1 (solution is either in the closed interval [0, p_max], or it does not exist). Complexity of this solution is O(n * p_max) in the worst case (plus the running time for calculating lcm!). There is a better solution regarding the time complexity, but it uses an additional binary array - classical time-space tradeoff. Its idea is similar to the Sieve of Eratosthenes, but for remainders instead of primes :)

p_max = lcm (p[0],p[1],...,p[n]) - 1;
int remainders[p_max + 1] = {0};
for i = 0 to n:
    int rem = s[i] - p[i];
    while rem >= -p_max:
        remainders[-rem] = 1;
        rem -= p[i];
for i = 0 to n:
    if !remainders[i]:
         return i;
return -1;

Explanation of the algorithm: first, we create an array remainders that will indicate whether certain negative remainder exists in the whole set. What is a negative remainder? It's simple, notice that 6 = 2 mod 4 is equivalent to 6 = -2 mod 4. If remainders[i] == 1, it means that if we add i to one of the s[j], we will get p[j] (which is 0, and that is what we want to avoid). Array is populated with all possible negative remainders, up to -p_max. Now all we have to do is search for the first i, such that remainder[i] == 0 and return it, if it exists - notice that the solution does not have to exists. In the problem text, you have indicated that you are searching for the minimum positive integer, I don't see why zero would not fit (if all s[i] are positive). However, if that is a strong requirement, just change the for loop to start from 1 instead of 0, and increment p_max. The complexity of this algorithm is n + sum (p_max / p[i]) = n + p_max * sum (1 / p[i]), where i goes from to 0 to n. Since all p[i]s are at least 2, that is asymptotically better than the brute force solution.

An example for better understanding: suppose that the input is (5,4), (5,1), (2,0). p_max is lcm(5,5,2) - 1 = 10 - 1 = 9, so we create array with 10 elements, initially filled with zeros. Now let's proceed pair by pair:

• from the first pair, we have remainders[1] = 1 and remainders[6] = 1
• second pair gives remainders[4] = 1 and remainders[9] = 1
• last pair gives remainders[0] = 1, remainders[2] = 1, remainders[4] = 1, remainders[6] = 1 and remainders[8] = 1.

Therefore, first index with zero value in the array is 3, which is a desired solution.