Day 20 - LeetCodee 172. Factorial Trailing Zeroes

LeetCodee 172. Factorial Trailing Zeroes

題目

Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.

翻譯

給一個正整數n，回傳n!中有幾個0
注意：你的解法應該是log(n)的時間複雜度。
範例： n = 5 ; n! = 120 回傳 1

n!: 代表一直連續不斷往下乘直到1為止？

想法

沒學過演算法, 應該不會懂..這題是要取有幾位數的0
總之, 當出現0就是10的Ｎ次方, 所以因子裡面一定含有2跟5,
真正決定會出現幾個0的, 是n!裡面出現幾個5

ex:
n = 5, 54321 = 120, 52 = 10, 因此會出現一個0
n = 10, 10987654321, 10 =[5, 2], 有2個5, 所以會出現2個0

n = 15 , 15, 10, 5 有3個5, 所以會出現3個0
n = 25, 會出現 25,20,15,10,5共5個帶有5的數字，不過25其實包含了55，所以25!總共會出現5+1=6個10。

詳細參閱

https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/172md.html
https://discuss.leetcode.com/topic/40298/javascript-solution-140ms

---

Code

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {

    let count = 0;

    if ( n < 5 ) {
        return count;
    }

    while ( n >= 5 ) {
        count += Math.floor( n / 5 );
        n = n / 5;
    }
    return count;
};

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {

    var ans = 0;
    //count the numbers of 5 in n!
    //ex. 25, ans = (25/5) + (5/5) = 6
    for ( var i = n; i > 0; i = Math.floor(i/5) ) {
        ans += Math.floor(i/5);
    }
    return ans;
};

Run