Can I take two variables a and b, and start traversing from 1 to 2000, and find factors of each number and store number of ‘2’ as factor in ‘a’ and no. of ‘5’ as factor in ‘b’…and lower of a and b will be the trailing zeroes for that particular number that is being traversed.
please check this approach, it has O(2000*2000) complexity
@jishangarg
The complexity is n*(log2n + log5n). But we need a method which can give us the answer in O(log(n)).
There was a method in Permutations and Combinations. Keep a variable ans set to 0. Keep dividing n by the required number, i.e, 2 and 5 and keep adding the quotient to ans , update n = n/num and keep doing it till n > 0. This way, you can find the number of 2’s and 5’s in n factorial.
If my explanation was able to resolve your doubt, please mark the query as resolved.
Please revert in case you face any difficulty.
how your method is giving the ans, plz explain the logic…
@jishangarg
Using the above method, I calcaulate the number of 5’s in n! and the number of 2’s in n!
Because 10 is made up of 5 and 2, the minimum of the count of 5 and 2 is the required answer.
If my explanation was able to clear your doubt, please mark the query as resolved.