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
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) + …
Then answer is f(N)+f(M)
C++
// CPP program for count number of trailing zeros// in N! * M!#include <iostream>using namespace std;// Returns number of zeros in factorial nint 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 programint 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 ndef 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 programN = 67M = 98print(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
<?php// PHP program for count number // of trailing zeros in N! * M!// Returns number of // zeros in factorial nfunction trailingZero($x){ // dividing x by powers of // 5 and update count $i = 5; $count = 0; while ($x > $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.?> |
Javascript
<script>// Javascript program for count number // of trailing zeros in N! * M!// Returns number of // zeros in factorial nfunction trailingZero(x){ // dividing x by powers of // 5 and update count let i = 5; let count = 0; while (x > i) { count = count + parseInt(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 Codelet N = 67; let M = 98;document.write(countProductTrailing(N, M));// This code is contributed by _saurabh_jaiswal.</script> |
Output:
37
Time Complexity: O(log5m+log5n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
