動機

也是有魔法的一題

  • 階乘中5的數量怎麼找?

Problem

Let f(x) be the number of zeroes at the end of x!. Recall that x! = 1 * 2 * 3 * ... * x and by convention, 0! = 1.

  • For example, f(3) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has two zeroes at the end.

Given an integer k, return the number of non-negative integers x have the property that f(x) = k.

 

Example 1:

Input: k = 0Output: 5Explanation: 0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.

Example 2:

Input: k = 5Output: 0Explanation: There is no x such that x! ends in k = 5 zeroes.

Example 3:

Input: k = 3Output: 5

 

Constraints:

  • 0 <= k <= 109

Sol

在階乘中5的數量一定比2少，所以找有幾個5就好 但要怎麼找?

def fives(n): # magic
  ret = 0
  while n > 0:
      ret += n//5
      n = n//5
  return ret

接著就是找有幾個 k-1 (k) .... k (k+1) k+1 ... 所以我們找lowerbound

class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        def fives(n): # magic
            ret = 0
            while n > 0:
                ret += n//5
                n = n//5
            return ret
        def lowerbound(k):
            a, b = 0, 5*(k+1)
            while a<b:
                mid = (a+b)//2
                if k > fives(mid):
                    a = mid+1
                else:
                    b = mid
            return a
        # k-1 (k) .... k (k+1) k+1 ...
        return lowerbound(k+1)-lowerbound(k)