Working on machines without understanding them ? Then you should be here..
Geographical location should not become a barrier to Share our knowledge.
Puzzles and Interview question are intended to be discussed here.
Hello Guys,
As a newbie on online Coding contests, I was initially fed-up with 1000000007.I hardly understood the logic behind it.
Some guys give an hint that "its the first 10 digit prime..", so what ?
There were 2 questions in my mind.
1) Why only a prime.
2) Why not 2nd or 3rd prime
Instantly I got an partial answer from myself for the first question, A prime because we need (ans % Prime) as the actual answer, so the o/p should be unique.
But, there was a lot behind that word Prime in this case (Explained later)
The 2nd question what still open, but lately I understood that 1000000007 is easy to represent as 10^9+7. Any greater Prime would have served the purpose but this was easy to write. Infact some times we find the 2nd 10 digit prime which is again easy to represent 1000000009.
This would have been very well understood by everyone now.
Coming to the actual point.
All of us might have noticed that 1000000007 comes only when our answers are expected to be very large, more commonly when we implement combinations n(c,k) or nCk.
We are asked mod operation with 1000000007 for 2 reasons,
1) Obviously, so as to restrict our answer to 10 digit and
2) Help us with large multiplications and divisions.
Did u read Division ? yes !!!
We must know that (%) is distributive over multiplication,addition etc, but not over division.
So, how to do large divisions ?
There`s a theorem known as "Fermat's little theorem".
It say`s that (A/B) % MOD = ((A % MOD)*(B^(MOD-2) % MOD))%MOD (You can refer wiki for actual theorem)
Now, we can see that, Fermat's theorem essentially convert all our division to multiplication.So we can use our mod (%) operation.
If you have any issues/queries, please comment the same... I will try my best to answer it.
As a newbie on online Coding contests, I was initially fed-up with 1000000007.I hardly understood the logic behind it.
Some guys give an hint that "its the first 10 digit prime..", so what ?
There were 2 questions in my mind.
1) Why only a prime.
2) Why not 2nd or 3rd prime
Instantly I got an partial answer from myself for the first question, A prime because we need (ans % Prime) as the actual answer, so the o/p should be unique.
But, there was a lot behind that word Prime in this case (Explained later)
The 2nd question what still open, but lately I understood that 1000000007 is easy to represent as 10^9+7. Any greater Prime would have served the purpose but this was easy to write. Infact some times we find the 2nd 10 digit prime which is again easy to represent 1000000009.
This would have been very well understood by everyone now.
Coming to the actual point.
All of us might have noticed that 1000000007 comes only when our answers are expected to be very large, more commonly when we implement combinations n(c,k) or nCk.
The combination formula is n!/(r!(n-r)!).
We are asked mod operation with 1000000007 for 2 reasons,
1) Obviously, so as to restrict our answer to 10 digit and
2) Help us with large multiplications and divisions.
Did u read Division ? yes !!!
We must know that (%) is distributive over multiplication,addition etc, but not over division.
So, how to do large divisions ?
There`s a theorem known as "Fermat's little theorem".
It say`s that (A/B) % MOD = ((A % MOD)*(B^(MOD-2) % MOD))%MOD (You can refer wiki for actual theorem)
Now, we can see that, Fermat's theorem essentially convert all our division to multiplication.So we can use our mod (%) operation.
If you have any issues/queries, please comment the same... I will try my best to answer it.
0 comments:
Post a Comment