Minimum total division remainder

Question

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

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

Is it possible to determine the minimum positive integer a, such that for each pair:

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

Anything better than brute force?

Answer 1

You can do better than brute force. The brute force will be O (A · n), where A is the minimum acceptable value for a that we are looking for.

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

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

The proposed algorithm is an effective way to generate numbers of this form (for all i and k), that is, invalid values ​​for a, in ascending order . As soon as the current value differs from the previous one by more than 1, this means that there is a valid intermediate.

The pseudocode is described below.

 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 

Note: it is possible that such a does not exist. If the real a is not found below LCM (p [1], p [2], ... p [n]), then the absence of real a is guaranteed.

---

An example is shown below. of how this algorithm works.

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

The first pair indicates that a should avoid values ​​such as 1, 3, 5, 7, ..., while the second pair indicates that we should avoid values ​​such as 2, 7, 12, 17, ....

The initial mini-heap contains the first element of each sequence (step 1 of the pseudocode) - in bold below:

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

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

We extract and remove the heap head, i.e. the minimum value among two bold, and this is 1 . We add the next element from this sequence to the heap, so the heap now contains elements 2 and 3:

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

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

We again extract the heap head, this time it contains the value 2 and adds the next element of this sequence to the heap:

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

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

The algorithm continues, we again select the value 3 and add 5 to the heap:

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

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

Finally, now we get the value 5 . At this stage, we understand that the value 4 is not among the invalid values ​​for a, so this is the solution we are looking for.

Answer 2

I can think of two different solutions. Firstly:

 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 guess this is what you call "brute force." Note that p_max represents the smallest total number from p[i] - 1 (the solution is either in the closed interval [0, p_max] or does not exist). The complexity of this solution is O(n * p_max) in the worst case (plus runtime to calculate lcm!). There is a better solution regarding time complexity, but it uses an extra binary array - a classic trade-off between time space. His idea is similar to the sieve of Eratosthenes, but for residues instead of prime numbers :)

 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; 

Algorithm Explanation: First, we create an array of remainders , which will indicate if there is a specific negative remainder in the entire set. What is a negative balance? Simply, note 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 s[j] , we get p[j] ( which is 0, and this is what we want to avoid). The array is filled with all possible negative residuals, up to -p_max . Now all we need to do is search for the first i , such that remainder[i] == 0 and return it if it exists - note that the solution should not exist. In the text of the problem, you indicated that you are looking for the minimum positive integer, I do not see why zero is not suitable (if all s[i] are positive). However, if this is a strong requirement, just change the for loop to start at 1 instead of 0 and increase 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 0 to n . Since all p[i] at least 2, that is, asymptotically better than brute force solutions.

An example for a better understanding: suppose the input is (5.4), (5.1), (2.0). p_max - lcm(5,5,2) - 1 = 10 - 1 = 9 , so we create an array of 10 elements, initially filled with zeros. Now let's say a couple after a couple:

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

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