Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

793. Preimage Size of Factorial Zeroes Function

Time: $O(\log_2 K \cdot \log_5 K$

Space: 

			


class Solution {
 public:
  int preimageSizeFZF(int k) {
    long l = 0;
    long r = 5L * k;

    while (l < r) {
      const long m = (l + r) / 2;
      if (trailingZeroes(m) >= k)
        r = m;
      else
        l = m + 1;
    }

    return trailingZeroes(l) == k ? 5 : 0;
  }

 private:
  // 172. Factorial Trailing Zeroes
  int trailingZeroes(long n) {
    return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
  }
};




			


class Solution {
  public int preimageSizeFZF(int k) {
    long l = 0;
    long r = 5 * (long) k;

    while (l < r) {
      final long m = (l + r) / 2;
      if (trailingZeroes(m) >= k)
        r = m;
      else
        l = m + 1;
    }

    return trailingZeroes(l) == k ? 5 : 0;
  }

  // 172. Factorial Trailing Zeroes
  private int trailingZeroes(long n) {
    return n == 0 ? 0 : (int) (n / 5 + trailingZeroes(n / 5));
  }
}