{"id":1057,"date":"2020-06-10T11:52:20","date_gmt":"2020-06-10T11:52:20","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1057"},"modified":"2022-03-28T01:33:58","modified_gmt":"2022-03-28T01:33:58","slug":"factorial-zeros","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/factorial-zeros\/","title":{"rendered":"Factorial Zeros"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Binary Search, Mathematics<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given a number N<\/code>, your task is to find the count of all such numbers that have N<\/code> trailing zeros in their factorial.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/h4>\n
Input : N = 2\n\nOutput : 5\n\nExplanation : \n\nAll these 5 numbers have 2 trailing zeros.\n\n10! = 3628800\n\n11! = 39916800\n\n12! = 479001600\n\n13! = 6227020800\n\n14! = 87178291200<\/code><\/pre>\n
OBSERVATION:<\/h3>\n
\n
    \n
  1. \n
    The solution of this problem will be either 0<\/code> or 5<\/code>.  <\/p>\n<\/li>\n
  2. \n
    0<\/code> if no such number is found whose factorial has N<\/code> trailing zeros.<\/p>\n<\/li>\n
  3. \n
    5<\/code> because if a number has N<\/code> trailing zeros then its 4 neigbouring numbers will also have the same trailing zeros.    <\/p>\n<\/li>\n<\/ol>\n
    For Example<\/em><\/strong>:
    \n(10, 11, 12 , 13, 14)<\/code> all will have 2 trailing zeros in their factorial. Similarly
    \n(15, 16, 17, 18, 19)<\/code> all will have 3 trailing zeros in their factorial.
    \nSimilary all such group of 5 numbers contain the same number of trailing zeros in their factorial.   <\/p>\n
    Important Point<\/em><\/strong>:
    \nWe just need to find a single number that has N<\/code> trailing zeros and our answer will be 5<\/code> else 0<\/code>.<\/p>\n
    Can we use Binary Search<\/code> here ?<\/em><\/strong>
    \nWe need to find a single number between 0<\/code> and 5*N<\/code> that has N<\/code> trailing zeros. We can use Binary Search<\/code> for efficiently searching it in Logarithmic Time Complexity<\/code>.<\/p>\n
    Why 5*N<\/code>?<\/em><\/strong>
    \n5*N<\/code> is the upper bound and any number whose factorial has N<\/code> trailing zeros will be less than the factorial of 5*N<\/code>.<\/p>\n<\/blockquote>\n
    SOLVING APPROACH:<\/h3>\n
    \n
      \n
    1. \n
      The idea is to use Binary Search<\/code>.  <\/p>\n<\/li>\n
    2. \n
      Initialize low<\/code> and high<\/code> as 0<\/code> and N*5<\/code>.<\/p>\n<\/li>\n
    3. \n
      Calculate mid = low + (high - low)\/2<\/code> and let us assume that mid is our required number with N<\/code> trailing zeros.<\/p>\n<\/li>\n
    4. \n
      Find trailing-zeros-of-mid<\/code> and compare it with N<\/code>, if both are equal return mid.<\/p>\n<\/li>\n
    5. \n
      Else if trailing-zeros-of-mid<\/code> > N<\/code>, this implies that our required number lies in the lower half so we update high = mid - 1<\/code>. <\/p>\n<\/li>\n
    6. \n
      Else (<\/code>trailing-zeros-of-mid<\/code> < N)<\/code> implies that our required number lies in the higher half so we update low = mid + 1<\/code>. And keep on searching for a feasible number till (low <= high)<\/code>, if post this condition number is not found return 0<\/code>.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
      ALGORITHM:<\/h3>\n
      i = 0\nj = 5 * N\nmid = (i + j) \/ 2 \n\nwhile i <= j\n\n  If trail_zeros_of_mid = N\n    print 5\n\n  else if trail_zeros_of_mid < N\n    i = mid + 1\n\n  else\n    j = mid - 1\n\nif i > j\n  print 0<\/code><\/pre>\n
      SOLUTIONS:<\/h3>\n
      \t\t\t\t\t\t