# Trailing number of 0s in product of two factorials

Given two integer N or M find the number of zero’s trailing in product of factorials (N!*M!)?

Examples:

```Input : N = 4, M = 5
Output :  1
Explanation : 4! = 24, 5! = 120
Product has only 1 trailing 0.

Input : N = 127!, M = 57!
Output : 44
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

As discussed in number of zeros in N! can be calculated by recursively dividing N by 5 and adding up the quotients.

For example if N = 127, then
Number of 0 in 127! = 127/5 + 127/25 + 127/125 + 127/625
= 25 + 5 + 1 + 0
= 31

Number of 0s in N! = 31. Similarly, for M we can calculate and add both of them.
So, by above we can conclude that number of zeroes in N!*M! Is equal to sum of number of zeroes in N! and M!.

f(N) = floor(N/5) + floor(N/5^2) + … floor(N/5^3) + …
f(M) = floor(x/5) + floor(M/5^2) + … floor(M/5^3) + …

## C++

 `// CPP program for count number of trailing zeros ` `// in N! * M! ` `#include ` `using` `namespace` `std; ` ` `  `// Returns number of zeros in factorial n ` `int` `trailingZero(``int` `x) ` `{ ` `    ``// dividing x by powers of 5 and update count ` `    ``int` `i = 5, count = 0; ` `    ``while` `(x > i) { ` `        ``count = count + x / i; ` `        ``i = i * 5; ` `    ``} ` `    ``return` `count; ` `} ` ` `  `// Returns count of trailing zeros in M! x N! ` `int` `countProductTrailing(``int` `M, ``int` `N) ` `{ ` `   ``return` `trailingZero(N) + trailingZero(M); ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `    ``int` `N = 67, M = 98; ` `    ``cout << countProductTrailing(N, M); ` `    ``return` `0; ` `} `

## Java

 `// Java program for count number ` `// of trailing zeros in N! * M! ` `import` `java.io.*; ` ` `  `class` `GFG { ` `     `  `    ``// Returns number of zeros in factorial n ` `    ``static` `int` `trailingZero(``int` `x) ` `    ``{ ` `        ``// dividing x by powers  ` `        ``// of 5 and update count ` `        ``int` `i = ``5``, count = ``0``; ` `         `  `        ``while` `(x > i) { ` `             `  `            ``count = count + x / i; ` `            ``i = i * ``5``; ` `        ``} ` `        ``return` `count; ` `    ``} ` `     `  `    ``// Returns count of trailing zeros in M! x N! ` `    ``static` `int` `countProductTrailing(``int` `M, ``int` `N) ` `    ``{ ` `    ``return` `trailingZero(N) + trailingZero(M); ` `    ``} ` `     `  `    ``// Driver program ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `N = ``67``, M = ``98``; ` `        ``System.out.println(countProductTrailing(N, M)); ` `    ``} ` `} ` ` `  ` `  `/* This code is contributed by Nikita Tiwari.*/`

## Python3

 `# Python 3 program for count ` `# number of trailing zeros ` `# in N ! * M ! ` ` `  `# Returns number of zeros in ` `# factorial n ` `def` `trailingZero(x) : ` ` `  `    ``# Dividing x by powers of 5 ` `    ``# and update count ` `    ``i ``=` `5` `    ``count ``=` `0` `     `  `    ``while` `(x > i) : ` `        ``count ``=` `count ``+` `x ``/``/` `i ` `        ``i ``=` `i ``*` `5` `     `  `    ``return` `count ` `     `  `# Returns count of trailing  ` `# zeros in M ! x N ! ` `def` `countProductTrailing(M, N) : ` `    ``return` `trailingZero(N) ``+` `trailingZero(M) ` `     `  `# Driver program ` `N ``=` `67` `M ``=` `98` `print``(countProductTrailing(N, M)) ` ` `  `# This code is contributed by Nikita Tiwari. `

## C#

 `// Java program for count number ` `// of trailing zeros in N! * M! ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Returns number of zeros in factorial n ` `    ``static` `int` `trailingZero(``int` `x) ` `    ``{ ` `        ``// dividing x by powers  ` `        ``// of 5 and update count ` `        ``int` `i = 5, count = 0; ` `         `  `        ``while` `(x > i) { ` `             `  `            ``count = count + x / i; ` `            ``i = i * 5; ` `        ``} ` `        ``return` `count; ` `    ``} ` `     `  `    ``// Returns count of trailing zeros in M! x N! ` `    ``static` `int` `countProductTrailing(``int` `M, ``int` `N) ` `    ``{ ` `    ``return` `trailingZero(N) + trailingZero(M); ` `    ``} ` `     `  `    ``// Driver program ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `N = 67, M = 98; ` `        ``Console.WriteLine(countProductTrailing(N, M)); ` `    ``} ` `} ` ` `  ` `  `/* This code is contributed by vt_m.*/`

## PHP

 ` ``\$i``)  ` `    ``{ ` `        ``\$count` `= ``\$count` `+ (int)(``\$x` `/ ``\$i``); ` `        ``\$i` `= ``\$i` `* 5; ` `    ``} ` `    ``return` `\$count``; ` `} ` ` `  `// Returns count of trailing  ` `// zeros in M! x N! ` `function` `countProductTrailing(``\$M``, ``\$N``) ` `{ ` `    ``return` `trailingZero(``\$N``) + trailingZero(``\$M``); ` `} ` ` `  `// Driver Code ` `\$N` `= 67; ``\$M` `= 98; ` `echo``(countProductTrailing(``\$N``, ``\$M``)); ` ` `  `// This code is contributed by Ajit. ` `?> `

Output:

``` 37
```