{"id":3452,"date":"2021-11-09T18:03:16","date_gmt":"2021-11-09T12:33:16","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3452"},"modified":"2021-11-09T18:03:16","modified_gmt":"2021-11-09T12:33:16","slug":"trailing-zeroes-in-factorial","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/trailing-zeroes-in-factorial\/","title":{"rendered":"Trailing Zeroes in Factorial"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#naive-approach\">Naive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><li><a href=\"#complexity-analysis\">Complexity Analysis<\/a><\/li><\/ul><li><a href=\"#optimal-approach\">Optimal Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><li><a href=\"#complexity-analysis\">Complexity Analysis<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a number <strong>n, <\/strong>find the number of trailing zeroes in <strong>n!<\/strong>.<\/p>\n\n\n\n<p id=\"-sample-test-cases-\"><strong>Sample Test Cases<\/strong><\/p>\n\n\n\n<p><strong>Input 1:<\/strong> n = 5<br><strong>Output 1:<\/strong> 1<br><strong>Explanation 1:<\/strong> 5! = 120 which has only 1 trailing zero.<\/p>\n\n\n\n<p><strong>Input 2:<\/strong> n = 100<br><strong>Output 2:<\/strong> 24<br><strong>Explanation 2:<\/strong> The number of trailing zeroes of 100! can be found to have 24 trailing zeroes.<\/p>\n\n\n\n<h2 id=\"naive-approach\">Naive Approach<\/h2>\n\n\n\n<p>The naive approach to solve this problem is to calculate the value of <strong>n!<\/strong> and then to find the number of trailing zeroes in it.<\/p>\n\n\n\n<p>We can find the number of trailing zeroes in a number by repeatedly dividing it by 10 until its last digit becomes non-zero.<\/p>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int getTrailingZeroes(int n) {\n  int factorial = 1;\n  for (int i = 1; i &lt;= n; i++) {\n    factorial *= i;\n  }\n  int zeroes = 0;\n  while (factorial % 10 == 0) {\n    zeroes++;\n    factorial \/= 10;\n  }\n  return zeroes;\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int getTrailingZeroes(int n) {\n  int factorial = 1;\n  for (int i = 1; i &lt;= n; i++) {\n    factorial *= i;\n  }\n  int zeroes = 0;\n  while (factorial % 10 == 0) {\n    zeroes++;\n    factorial \/= 10;\n  }\n  return zeroes;\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def getTrailingZeroes(n):\n    factorial = 1\n    zeroes = 0\n    for i in range(1, n + 1):\n        factorial *= i\n    while factorial % 10 == 0:\n        factorial \/\/= 10\n        zeroes += 1\n    return zeroes<\/pre>\n\n\n\n<h3 id=\"complexity-analysis\"><span id=\"complexity-analysis-2\">Complexity Analysis<\/span><\/h3>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(n)<\/li><li><strong>Space Complexity:<\/strong> O(1)<\/li><\/ul>\n\n\n\n<h2 id=\"optimal-approach\">Optimal Approach<\/h2>\n\n\n\n<p>Observe that number of trailing zeroes in a number will be the highest power of 10 present in the number.&nbsp;<\/p>\n\n\n\n<p>Now we know that <strong>10<\/strong><strong><sup>n<\/sup><\/strong><strong> = 2<\/strong><strong><sup>n<\/sup><\/strong><strong> * 5<\/strong><strong><sup>n<\/sup><\/strong>. So, the highest power of 10 will be equal to the minimum of the highest power of 2 and the highest power of 5 present in <strong>n!<\/strong>. We can observe that the highest power of 2 is always going to be less than or equal to the highest power of 5 in any value of <strong>n!<\/strong>. So, our problem boils down to finding the highest power of 5 in <strong>n!<\/strong>.<\/p>\n\n\n\n<p>The highest power of a prime number <strong>p<\/strong>, present in any factorial is given by a formula known as <strong>Legendre\u2019s Formula<\/strong>,&nbsp;<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"669\"  height=\"307\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3498 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 669px) 100vw, 669px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1.png 669w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1-300x138.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1-380x174.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1-550x252.png 550w\" ><\/figure>\n\n\n\n<p>Where <strong>V<\/strong><strong><sub>p<\/sub><\/strong><strong>(n!)<\/strong> represents the highest exponent in <strong>p<\/strong>, such that <strong>p<\/strong><strong><sup>n<\/sup><\/strong> divides <strong>n!<\/strong> where <strong>p<\/strong> is a prime number.<\/p>\n\n\n\n<p>For the number of trailing zeroes, the above formula transforms to,&nbsp;<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"338\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3500 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1-2-1024x338.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1-2-1024x338.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1-2-300x99.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1-2-768x254.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1-2-1536x507.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1-2-380x125.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1-2-550x182.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1-2-800x264.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1-2-1160x383.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-1-2.png 1875w\" ><\/figure>\n\n\n\n<p>Where k = <strong>floor of log<sub>5<\/sub>n<\/strong>.<\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int getTrailingZeroes(int n) {\n  int zeroes = 0;\n  int power = 5;\n  for (int i = 1;; i++) {\n    zeroes += (n \/ power);\n    if (n \/ power == 0) {\n      break;\n    }\n    power *= 5;\n  }\n  return zeroes;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int getTrailingZeroes(int n) {\n  int zeroes = 0;\n  int power = 5;\n  for (int i = 1;; i++) {\n    zeroes += (n \/ power);\n    if (n \/ power == 0) {\n      break;\n    }\n    power *= 5;\n  }\n  return zeroes;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def getTrailingZeroes(n):\n    zeroes = 0\n    power = 5\n    while (n \/\/ power) != 0:\n        zeroes += n \/\/ power\n        power *= 5\n    return zeroes<\/pre>\n\n\n\n<h3 id=\"complexity-analysis\">Complexity Analysis<\/h3>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(log<sub>5<\/sub>n)<\/li><li><strong>Space Complexity:<\/strong> O(1)<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<p id=\"-practice-problem-\"><strong>Practice Problem<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/old\/problems\/trailing-zeros-in-factorial\/\" target=\"_blank\" rel=\"noreferrer noopener\">Trailing Zeros<\/a><\/p>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>Q. What is the main drawback of the naive approach?<\/strong><br>A. The main drawback of the naive approach is that it calculates the factorial of <strong>n <\/strong>before computing the result, whose value can grow very large extremely quickly and can cause an overflow issue.<\/p>\n\n\n\n<p><strong>Q. How is the time complexity of the optimal approach calculated?<\/strong><br>A. In the optimal approach, n is divided by 5 at each iteration till it reaches 0. So the number of iterations till which the algorithm will continue is equal to <strong>floor(log<sub>5<\/sub>n)<\/strong>, which is our required time complexity.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a number n, find the number of trailing zeroes in n!. Sample Test Cases Input&hellip;\n","protected":false},"author":5,"featured_media":3503,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[543],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3452"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3452"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3452\/revisions"}],"predecessor-version":[{"id":3502,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3452\/revisions\/3502"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3503"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3452"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3452"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3452"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}