Given an integer n, find the number of positive integers whose factorial ends with n zeros. 
 
Example 1:
Input:
N = 1
Output: 5
Explanation:
5! = 120, 6! = 720, 7! = 5040, 
8! = 40320 and 9! = 362880.
 
Example 2:
Input:
N = 5
Output: 0
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countZeroes() which takes the integer N as input parameters and returns the count of positive numbers whose factorial ends with N zeros.
Expected Time Complexity: O(log(n))
Expected Auxiliary Space: O(1)
 
Constraints:
1<=N<=1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Sorting

Mathematics

Starter code: #User function Template for python3

class Solution:
    def countZeroes (self, n):
        # code here



Solutions:
class Solution:

	def cal(self, n):
		count = 0
		i = 5
		while True:
			if n // i >= 1:
				count = count + n // i
				i = i * 5
			else:
				break
		return count

	def countZeroes(self, n):
		obj = Solution()
		low = 1
		high = n * 5
		ans = 0
		while low <= high:
			mid = low + (high - low) // 2
			temp = obj.cal(mid)
			if temp == n:
				ans = mid
				break
			elif temp > n:
				high = mid - 1
			else:
				low = mid + 1
		if ans == 0:
			return 0
		return 5


class Solution:

	def count_fives(self, num):
		result = 0
		i = 5
		while num // i > 0:
			result += num // i
			i *= 5
		return result

	def countZeroes(self, n):
		l = 0
		r = n * 5
		while l <= r:
			mid = (l + r) // 2
			cnt = self.count_fives(mid)
			if cnt == n:
				return 5
			if cnt > n:
				r = mid - 1
			else:
				l = mid + 1
		return 0


class Solution:

	def count(self, a):
		c = 0
		while a:
			a = a // 5
			c += a
		return c

	def solve(self, n):
		i = 1
		e = 5 * n
		ans = 0
		while i <= e:
			mid = (i + e) // 2
			if self.count(mid) >= n:
				ans = mid
				e = mid - 1
			else:
				i = mid + 1
		return ans

	def countZeroes(self, n):
		return self.solve(n + 1) - self.solve(n)


import math

class Solution:

	def countZeroes(self, n):
		if n == 1:
			return 5

		def check(p, n):
			temp = p
			count = 0
			f = 5
			while f <= temp:
				count += temp // f
				f *= 5
			if count >= n:
				return True
			return False
		low = 0
		high = 5 * n
		lis = []
		while low < high:
			mid = (low + high) // 2
			if check(mid, n):
				high = mid
			else:
				low = mid + 1
		k = low
		j = math.factorial(k)
		j = str(j)
		count = 0
		for i in range(len(j) - 1, len(j) - n - 2, -1):
			if j[i] == '0':
				count += 1
		if count != n:
			return 0
		return 5


def trailingZeroes(n):
	cnt = 0
	while n > 0:
		n = int(n / 5)
		cnt += n
	return cnt

def binarySearch(n):
	low = 0
	high = 1000000.0
	while low < high:
		mid = int((low + high) / 2)
		count = trailingZeroes(mid)
		if count < n:
			low = mid + 1
		else:
			high = mid
	result = 0
	while trailingZeroes(low) == n:
		result += 1
		low += 1
	return result

class Solution:

	def countZeroes(self, n):
		return binarySearch(n)


class Solution:

	def trailing_zeros(self, n):
		num = 1
		res = 0
		while num:
			ans = 0
			i = 1
			power = 5 ** i
			while power <= num:
				ans += num // power
				i += 1
				power = 5 ** i
			if ans == n:
				res += 1
			elif ans > n:
				break
			num += 1
		return res

	def countZeroes(self, n):
		return self.trailing_zeros(n)


def zero_cnt(a):
	i = 5
	cnt = 0
	while a >= i:
		cnt += a // i
		i *= 5
	return cnt

class Solution:

	def countZeroes(self, n):
		i = 0
		j = 100000000
		while i <= j:
			mid = (i + j) // 2
			if zero_cnt(mid) == n:
				return 5
			elif zero_cnt(mid) < n:
				i = mid + 1
			else:
				j = mid - 1
		return 0
if __name__ == '__main__':
	ob = Solution()
	t = int(input())
	for _ in range(t):
		N = int(input())
		ans = ob.countZeroes(N)
		print(ans)


class Solution:

	def countZeroes(self, n):
		low = 1
		high = 1000000.0
		result = 0
		while low <= high:
			mid = int(low + (high - low) / 2)
			trailZeroes = self.trailingZeroes(mid)
			if trailZeroes == n:
				result = 5
				high = mid - 1
			elif trailZeroes < n:
				low = mid + 1
			else:
				high = mid - 1
		return result

	def trailingZeroes(self, n):
		cnt = 0
		while n > 0:
			n = int(n / 5)
			cnt += n
		return cnt


class Solution:

	def countZeroes(self, n):
		if n == 1:
			return 5
		count = 0

		def zerocount(k):
			zc = 0
			while k != 0:
				k = k // 5
				zc += k
			return zc
		low = 0
		high = 1000000.0
		while low < high:
			mid = (low + high) // 2
			zcm = zerocount(mid)
			if zcm >= n:
				high = mid
			else:
				low = mid + 1
			if zcm == n:
				return 5
		return 0


class Solution:

	def trailingZeroes(self, n):
		cnt = 0
		while n > 0:
			n = int(n / 5)
			cnt += n
		return cnt

	def countZeroes(self, n):
		low = 0
		high = 100000
		while low < high:
			mid = int((low + high) / 2)
			count = self.trailingZeroes(mid)
			if count < n:
				low = mid + 1
			else:
				high = mid
		result = []
		while self.trailingZeroes(low) == n:
			result.append(low)
			low += 1
		return len(result)


class Solution:

	def number_of_zeroes(self, n):
		res = 0
		value = 5
		while value <= n:
			res += n // value
			value *= 5
		return res

	def countZeroes(self, n):
		low = 0
		high = 5 * n
		while low < high:
			mid = (low + high) // 2
			noz = self.number_of_zeroes(mid)
			if noz < n:
				low = mid + 1
			else:
				high = mid
		ans = 0
		while self.number_of_zeroes(low) == n:
			ans += 1
			low += 1
		return ans


class Solution:

	def num_zeros(self, five_k):
		num = five_k * 5
		zeros = 0
		tmp = 5
		while num // tmp > 0:
			zeros += num // tmp
			tmp *= 5
		return zeros

	def countZeroes(self, n):
		left = 0
		right = n
		while left <= right:
			mid = left + (right - left) // 2
			num = self.num_zeros(mid)
			if num == n:
				return 5
			if num < n:
				left = mid + 1
			else:
				right = mid - 1
		return 0


class Solution:

	def count0(self, n):
		c = 0
		while n > 0:
			n = int(n / 5)
			c += n
		return c

	def countZeroes(self, n):
		lo = 0
		hi = 1000000.0
		while lo < hi:
			mid = int((lo + hi) / 2)
			c = self.count0(mid)
			if c < n:
				lo = mid + 1
			else:
				hi = mid
		m = 0
		while self.count0(lo) == n:
			m += 1
			lo += 1
		return m


class Solution:

	def countZeroes(self, n):
		smallestnumwithatleastnzeros = self.Helper(n)
		smallestnumwithatleastnplusonezeros = self.Helper(n + 1)
		return smallestnumwithatleastnplusonezeros - smallestnumwithatleastnzeros

	def Helper(self, n):
		low = 0
		high = 5 * n
		while low <= high:
			mid = low + (high - low) // 2
			if self.check(mid, n):
				high = mid - 1
			else:
				low = mid + 1
		return low

	def check(self, val, n):
		count = 0
		f = 5
		while f <= val:
			count += val // f
			f = f * 5
		if count >= n:
			return True
		else:
			return False