Preimage Size of Factorial Zeroes Function

// Accepted solution for LeetCode #793: Preimage Size of Factorial Zeroes Function
class Solution {
    public int preimageSizeFZF(int k) {
        return g(k + 1) - g(k);
    }

    private int g(int k) {
        long left = 0, right = 5 * k;
        while (left < right) {
            long mid = (left + right) >> 1;
            if (f(mid) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return (int) left;
    }

    private int f(long x) {
        if (x == 0) {
            return 0;
        }
        return (int) (x / 5) + f(x / 5);
    }
}

// Accepted solution for LeetCode #793: Preimage Size of Factorial Zeroes Function
func preimageSizeFZF(k int) int {
	f := func(x int) int {
		res := 0
		for x != 0 {
			x /= 5
			res += x
		}
		return res
	}

	g := func(k int) int {
		left, right := 0, k*5
		for left < right {
			mid := (left + right) >> 1
			if f(mid) >= k {
				right = mid
			} else {
				left = mid + 1
			}
		}
		return left
	}

	return g(k+1) - g(k)
}

# Accepted solution for LeetCode #793: Preimage Size of Factorial Zeroes Function
class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        def f(x):
            if x == 0:
                return 0
            return x // 5 + f(x // 5)

        def g(k):
            return bisect_left(range(5 * k), k, key=f)

        return g(k + 1) - g(k)

// Accepted solution for LeetCode #793: Preimage Size of Factorial Zeroes Function
/**
 * [0793] Preimage Size of Factorial Zeroes Function
 *
 * 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 = 0
 * Output: 5
 * Explanation: 0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.
 *
 * Example 2:
 *
 * Input: k = 5
 * Output: 0
 * Explanation: There is no x such that x! ends in k = 5 zeroes.
 *
 * Example 3:
 *
 * Input: k = 3
 * Output: 5
 *
 *  
 * Constraints:
 *
 * 	0 <= k <= 10^9
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/
// discuss: https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn preimage_size_fzf(k: i32) -> i32 {
        let mut nums = vec![0; 13];
        let mut k = k;
        nums[0] = 1;

        for i in 1..13 {
            nums[i] = 5 * nums[i - 1] + 1;
        }

        for i in (0..13).rev() {
            let num = nums[i];
            if k / num == 5 {
                return 0;
            }
            k %= nums[i];
        }
        5
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_0793_example_1() {
        let k = 0;
        let result = 5;

        assert_eq!(Solution::preimage_size_fzf(k), result);
    }

    #[test]
    fn test_0793_example_2() {
        let k = 5;
        let result = 0;

        assert_eq!(Solution::preimage_size_fzf(k), result);
    }

    #[test]
    fn test_0793_example_3() {
        let k = 3;
        let result = 5;

        assert_eq!(Solution::preimage_size_fzf(k), result);
    }
}

// Accepted solution for LeetCode #793: Preimage Size of Factorial Zeroes Function
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #793: Preimage Size of Factorial Zeroes Function
// class Solution {
//     public int preimageSizeFZF(int k) {
//         return g(k + 1) - g(k);
//     }
// 
//     private int g(int k) {
//         long left = 0, right = 5 * k;
//         while (left < right) {
//             long mid = (left + right) >> 1;
//             if (f(mid) >= k) {
//                 right = mid;
//             } else {
//                 left = mid + 1;
//             }
//         }
//         return (int) left;
//     }
// 
//     private int f(long x) {
//         if (x == 0) {
//             return 0;
//         }
//         return (int) (x / 5) + f(x / 5);
//     }
// }