Competitive programming is not just about knowing programming syntax—it’s a blend of logic, speed, and mathematics. Mastering a few essential math tricks can drastically boost your problem-solving skills and efficiency.
Let’s explore the most powerful and commonly used math techniques in competitive programming.
Table of Contents
Number of times a prime p exist in n!
count_of_p = n//p + n//p^2 + n//p^3........
Example find no. of trailing zero in 100!
- Zero is formed by 2*5
no_of_2 = 100/2 +100//4 + 100//8 + 100/16 + 100/32 + 100/64 + 100/128
= 50 + 25 + 12 + 6 + 3 + 1 + 0 .....
= 97no_of_5 = 100//5 + 100//25 + 100//125
= 20 + 4 + 0
= 24So, no of zero min(no_of_2,no_of_5) = 24