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.
Finding the time and actual effort to create a superb article like this is great thing. I’ll learn many new stuff right here! Good luck for the next post buddy..
ReplyDeleteSoftware Testing Services USA
Software Testing Company USA
Functional Testing Services
QA Automation Testing Services
eCommerce Testing Services
Performance Testing Services
Security Testing Services
API Testing Services
Regression Testing Services
Mobile App Testing Services
Download Video Player | Windows Media Player | Best Media Player
ReplyDeleteNice 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.
ReplyDeleteFeatures @ 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