Doubt in SETDIFF

general
,
1

This is the question [LINK][1]

Here is my code for SETDIFF(


[2]).

I think my logic behind the solution is right. 
 I guess there is some error because of MOD operation.

Can someone point that out?
Thanks!


  [1]: https://www.codechef.com/problems/SETDIFF
  [2]: https://www.codechef.com/viewsolution/14667896
2

You are right, the error is in the modulo operation. “(P + MOD - Q) % MOD” is guaranteed to be positive only if both P and Q are less than MOD. But in your code, you are doing “P += (a[i] * (start - 1)) % MOD”, which means that on every iteration, some value < MOD is added to P. So the final value of P ends up being < N × MOD. Clearly it may not be < MOD. The same applies to Q. In such a case P + MOD - Q may be a negative value, which will result in a wrong answer.

There are two ways to fix this

  1. Change “P += (a[i] * (start - 1)) % MOD” to “P = (P + a[i] * (start - 1)) % MOD”, and same for Q.
  2. Change “(P + MOD - Q) % MOD” to “(((P - Q) % MOD) + MOD) % MOD” or “(P % MOD + MOD - Q % MOD) % MOD”.
    Both ways make sure that the answer remains positive.
1 Like