Note: Your solution should be in logarithmic time complexity.
public class Solution { public int trailingZeroes(int n) { // http://en.wikipedia.org/wiki/Trailing_zero // Non-negative number doesn't have factorial. // The factorial of 0 is 1. if (n <= 0) return 0; // Find k so that pow(5, k+1) > n. // Add 0.1 to n in case pow(5, k+1) = n. int k = (int)Math.ceil(Math.log(n+0.1)/Math.log(5.0)-1); if (k < 1) return 0; // The number of trailing zeros int ntz = 0; for (int i = 1; i <= k; i++) ntz += n/Math.pow(5, i); return ntz; } }
No comments:
Post a Comment