Skip to content

793. Preimage Size of Factorial Zeroes Function 👍

  • Time: $O(\log_2 K \cdot \log_5 K$
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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:
  // Same as 172. Factorial Trailing Zeroes
  int trailingZeroes(long n) {
    return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
  }

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