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.

5 comments:

  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

    For more information visit our website at Best Media Player - CnX Player

    ReplyDelete
  2. Thanks for the always useful information. This is great information to help peoples and nice article written by writer. CnX Player is a powerful & efficient 4K ultra HD enabled video player for Windows 10 PC & Tablet, Android and iOS – iPhone & iPad.

    Download Media Player for Windows 10 - Microsoft Store
    Download Video Player for Android from Google Play
    Download Video Player for iPhone/iPad from Apple App Store

    ReplyDelete