## Sunday, June 21, 2020

### Modulo Operation Tricks

When you solve a problem that might result in values beyond integer limits (e.g., Wouldn't fit into a 64bit integer), you're often asked to print the value modulo a significant prime value (e.g. 10^9 + 1).

To be able to use the modulo operation correctly, you need to understand its properties.

Trick #1 Multiplication/Summation of values

For example, if you are multiplying/adding a set of numbers (a, b, c, d) then its useful to know that:

`(a*b*c*d)%N = (a%N)*(b%N)(c%N)*(d%N) = ((a*b*c)%N)*d%N`

The above is quite useful when you want to always keep calculations to fit into the given limits.

Trick #2 Multiplicative Inverse

For division, it's a little bit tricky though, you can't merely assume that:

`(a/b)%N = (a%N/b%N)`

Although that would be awesome, it's unfortunately not correct - So to solve this, you have to understand the modular multiplicative inverse of a number A.

So to calculate (a/b)%N, you can convert it to a%N*power(b, N-2) - I will not explain how or why, please refer to the wiki page above for more details.

Trick #3 Negative Numbers

Another problem one would face during programming contests is when you calculate modulo for a negative number, which doesn't really work as intended.

So -1%10 would result in -1 rather than 9 - This really depends on the programming language you use but this trick is useful for Java and C++ but not for Python which produces the right value 😊.

To overcome this, you can calculate it by adding N to the number so, -1%10 = 9%10 = 9 👍.

That's it! I will keep this post up to date with any other tricks I find in the future.

1. Nice Post, CnX Player offers a fantastic Video Casting feature that gives an absolute freedom to all its users to cast ANY (literally ANY) video format and ANY video codec from PC to TV within a fraction of seconds! It is a Best Media Player.

Features @ CnX Player - Best Media Player

* Stream ANY video from PC to Chromecast
* Cast ALL Videos From PC To All Smart TV
* Stream ANY video from PC to Chromecast
* Cast Videos from iPhone iPad to Firestick TV
* Stream any videos from PC to MI TV
* Cast ALL Videos from PC to Android TV
* Stream ANY Video From PC To SAMSUNG TV