Given a number n. The task is to find the smallest number whose factorial contains at least n trailing zeroes.
Example 1:
Input:
n = 1
Output: 5
Explanation : 5! = 120 which has at
least 1 trailing 0.
Example 2:
Input:
n = 6
Output: 25
Explanation : 25! has at least
6 trailing 0.
User Task:
Complete the function findNum() which takes an integer N as input parameters, and returns the answer.
Expected Time Complexity: O(log_{2} N * log_{5} N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= n <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Mathematics

Complete search

Starter code: #User function Template for python3



class Solution:

    def findNum(self, n : int):

        # Complete this function

Solutions:
class Solution:

	def findNum(self, n: int):
		count = 0
		num = 5
		while True:
			temp = num
			while temp % 5 == 0:
				count += 1
				temp //= 5
			if count >= n:
				return num
			num += 5


class Solution:

	def findNum(self, n: int):
		count = 0
		for i in range(5, 100000, 5):
			num = i
			while num % 5 == 0:
				num = num / 5
				count += 1
				if count == n:
					return i


import math

class Solution:

	def findNum(self, n: int):
		if n == 1:
			return 5
		s = 1
		c = 0
		for h in range(5, 100000, 5):
			i = h
			while i > 0:
				if i % 5 == 0:
					c += 1
					i //= 5
					if c == n:
						return h
				else:
					break


class Solution:

	def findNum(self, n: int):
		low = 0
		high = 5 * n
		while low <= high:
			mid = (low + high) // 2
			count = 0
			i = 5
			while i <= mid:
				count += mid // i
				i *= 5
			if count >= n:
				high = mid - 1
			else:
				low = mid + 1
		return low


class Solution:

	def cfive(self, m):
		c = 0
		while m:
			c += m // 5
			m = m // 5
		return c

	def findNum(self, n: int):
		s = 1
		e = 5 * n
		while s <= e:
			m = (s + e) // 2
			nfive = self.cfive(m)
			if nfive >= n:
				ans = m
				e = m - 1
			if nfive < n:
				s = m + 1
		return ans


class Solution:

	def findNum(self, n: int):

		def check(num, n):
			p = 5
			cnt = 0
			while p <= num:
				cnt += num // p
				p = p * 5
			return n <= cnt
		if n == 1:
			return 5
		l = 0
		h = 5 * n
		ans = 0
		while l < h:
			mid = (l + h) // 2
			if check(mid, n):
				h = mid
			else:
				ans = mid + 1
				l = mid + 1
		return ans


import math

class Solution:

	def find_zeroes_in_fact(self, x):
		denom = 5
		zeroes = 0
		while x >= denom:
			zeroes += int(x / denom)
			denom *= 5
		return zeroes

	def findNum(self, n: int):
		low = 0
		high = n * 5
		ans = 0
		while low <= high:
			mid = int((low + high + 1) / 2)
			zeroes = Solution().find_zeroes_in_fact(mid)
			if zeroes >= n:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def findNum(self, n: int):

		def poss(num, n):
			temp = num
			count = 0
			f = 5
			while f <= temp:
				count += temp // f
				f = f * 5
			return count >= n
		if n == 1:
			return 5
		l = 5
		h = 5 * n
		while l <= h:
			m = l + (h - l) // 2
			if poss(m, n):
				h = m - 1
			else:
				l = m + 1
		return l


class Solution:

	def findNum(self, n: int):

		def poss(p, n):
			temp = p
			count = 0
			f = 5
			while f <= temp:
				count += temp // f
				f = f * 5
			return count >= n
		if n == 1:
			return 5
		low = 0
		high = 5 * n
		while low < high:
			mid = low + high >> 1
			if poss(mid, n):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def solve(self, x):
		zeros = 0
		denon = 5
		while x >= denon:
			zeros += x // denon
			denon = denon * 5
		return zeros

	def findNum(self, n: int):
		l = 0
		h = 5 * n
		ans = 0
		while l <= h:
			mid = (l + h) // 2
			zeros = self.solve(mid)
			if zeros >= n:
				ans = mid
				h = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def find_the_num(self, x):
		zeros = 0
		deno = 5
		while x >= deno:
			zeros += x // deno
			deno = deno * 5
		return zeros

	def findNum(self, n: int):
		l = 0
		h = 5 * n
		ans = 0
		while l <= h:
			mid = (l + h) // 2
			zeros = self.find_the_num(mid)
			if zeros >= n:
				ans = mid
				h = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def findNum(self, n: int):
		ans = 0
		left = 0
		right = n * 5
		while right >= left:
			mid = (left + right) // 2
			zeros = self.factorial(mid)
			if zeros >= n:
				ans = mid
				right = mid - 1
			else:
				left = mid + 1
		return ans

	def factorial(self, num):
		count = 0
		deno = 5
		while num >= deno:
			count += num // deno
			deno = 5 * deno
		return count


def f(x: int):
	xx = x
	ans = 0
	while xx:
		ans += xx // 5
		xx //= 5
	return ans

def f_inverse(n):
	l = 0
	r = 10 ** 9
	while l < r:
		mid = (l + r) // 2
		if f(mid) >= n:
			r = mid
		else:
			l = mid + 1
	return l

class Solution:

	def findNum(self, n: int):
		return f_inverse(n)


class Solution:

	def findNum(self, n: int):

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


class Solution:

	def findNum(self, n: int):
		l = 0
		h = n * 5
		ans = 0
		while l <= h:
			m = (l + h) // 2
			countOf5 = self.count(m)
			if countOf5 >= n:
				ans = m
				h = m - 1
			else:
				l = m + 1
		return ans

	def count(self, m):
		count = 0
		val = 5
		while val <= m:
			count += m // val
			val = val * 5
		return count


class Solution:

	def findNum(self, n: int):

		def isok(num):
			n_zeros = 0
			j = num
			d = 5
			while j >= d:
				n_zeros += j // d
				d *= 5
			return n_zeros
		low = 0
		high = 5 * n
		res = 0
		while low <= high:
			mid = (low + high) // 2
			if isok(mid) >= n:
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


class Solution:

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

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


class Solution:

	def findNum(self, n: int):

		def fives(n):
			count = 0
			while n:
				if n % 5 != 0:
					break
				n = n // 5
				count += 1
			return count
		x = 0
		factorial = 0
		while x < n:
			factorial += 5
			x += fives(factorial)
		return factorial


class Solution:

	def findNum(self, n: int):
		fact = 24
		s = 5
		zeros = 10
		while n > 0:
			fact = fact * s
			temp = s
			count = 0
			while temp >= 5:
				temp //= 5
				count += temp
			if count >= n:
				return s
			s += 5
		return s - 1


from math import factorial

class Solution:

	def zero_count(self, x):
		denome = 5
		zeros = 0
		while x >= denome:
			zeros += x // denome
			denome *= 5
		return zeros

	def findNum(self, n: int):
		low = 0
		high = n * 5
		ans = low
		while low <= high:
			mid = (low + high) // 2
			zeros = self.zero_count(mid)
			if zeros >= n:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def findNum(self, n: int):
		d = 0
		i = 1
		while d < n:
			k = 5 * i
			while k % 5 == 0:
				d += 1
				k = k / 5
			i += 1
		return (i - 1) * 5


class Solution:

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

		def check(m, n):
			res = 0
			while m >= 5:
				m = m // 5
				res += m
			return res < n
		l = 0
		u = 5 * n
		while l < u:
			m = (l + u) // 2
			if check(m, n):
				l = m + 1
			else:
				u = m
		return l


class Solution:

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

	def check(self, p: int, n: int):
		temp = p
		count = 0
		f = 5
		while f <= temp:
			count += temp // f
			f *= 5
		return count >= n


import math

class Solution:

	def find(self, mid, n):
		count = 0
		temp = 5
		while temp <= mid:
			count = count + mid // temp
			temp = temp * 5
		return count >= n

	def findNum(self, n: int):
		if n == 1:
			return 5
		l = 0
		r = n * 5
		ans = 0
		while l < r:
			mid = (l + r) // 2
			if self.find(mid, n):
				r = mid
				ans = mid
			else:
				l = mid + 1
		return l


class Solution:

	def findNum(self, n: int):
		k = 1
		count = 0
		while count < n:
			k += 1
			x = k
			while x % 5 == 0:
				count += 1
				x //= 5
		return k


class Solution:

	def findNum(self, n: int):

		def trail(ni):
			a = 0
			if ni > 4:
				while True:
					ni = ni // 5
					a = a + ni
					if ni < 5:
						break
			return a
		l = 1
		h = 5 * 10 ** 4
		while l <= h:
			mid = l + h >> 1
			if trail(mid) >= n:
				h = mid - 1
			else:
				l = mid + 1
		return l


class Solution:

	def findNum(self, n: int):

		def numberOfzeros(x):
			denom = 5
			zeros = 0
			while x >= denom:
				zeros += x // denom
				denom *= 5
			return zeros
		low = 0
		high = 5 * n
		ans = low
		while low <= high:
			mid = (low + high) // 2
			zeros = numberOfzeros(mid)
			if zeros >= n:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def findNum(self, n: int):
		if n < 6:
			return 5 * n
		k = 1
		ans = 0
		limit_k = 1
		cumsum = [1]
		while limit_k < n:
			limit_k += 5 ** k
			cumsum.append(limit_k)
			k += 1
		ans = 5 ** k
		k -= 1
		l = cumsum[k - 1]
		limit_k -= 1
		while True:
			if limit_k - k + 1 <= n <= limit_k + 1:
				return ans
			else:
				limit_k -= l
				ans -= 5 ** k
			if limit_k < n:
				limit_k += l
				ans += 5 ** k
				limit_k -= 1
				k -= 1
				l = cumsum[k - 1]


class Solution:

	def findNum(self, n: int):

		def numOfZeros(num):
			c = 0
			while num >= 5:
				num //= 5
				c += num
			return c
		(l, h) = (1, 1000000000)
		while l < h:
			mid = l + (h - l) // 2
			if numOfZeros(mid) < n:
				l = mid + 1
			else:
				h = mid
		return l


class Solution:

	def count(self, n):
		ans = 0
		ch = 5
		while n >= ch:
			ans += n // ch
			ch *= 5
		return ans

	def findNum(self, n: int):
		l = 1
		while self.count(l) < n:
			l *= 5
		(l, r) = (l // 5, l)
		res = r
		while l <= r:
			m = (l + r) // 2
			if self.count(m) >= n:
				res = m
				r = m - 1
			else:
				l = m + 1
		return res


class Solution:

	def findNum(self, n: int):

		def zero_count(n):
			temp = n
			count = 0
			f = 5
			while f <= temp:
				count += temp // f
				f = f * 5
			return count
		left = 0
		right = n * 5
		ans = right
		while left <= right:
			mid = (left + right) // 2
			current = zero_count(mid)
			if current < n:
				left = mid + 1
			else:
				ans = min(ans, mid)
				right = mid - 1
		return ans


import math

class Solution:

	def findNum(self, n: int):
		low = 5
		high = n * 5
		while low <= high:
			mid = (low + high) // 2
			(summ, midd) = (0, mid)
			while midd > 0:
				summ += midd // 5
				midd = midd // 5
			if summ >= n:
				high = mid - 1
			else:
				low = mid + 1
		return int(low)


class Solution:

	def findNum(self, n: int):
		l = 1
		r = int(100000.0)
		ans = -1

		def zero(x):
			count = 0
			while x > 0:
				count += x // 5
				x = x // 5
			return count
		while l <= r:
			mid = (l + r) // 2
			val = zero(mid)
			if val >= n:
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def countZero(p, n):
		fives = 5
		count = 0
		val = p
		while fives <= val:
			count += val // fives
			fives *= 5
		return count >= n

	def findNum(self, n: int):
		low = 0
		high = 5 * n
		if n == 1:
			return 5
		while low < high:
			mid = low + high >> 1
			if Solution.countZero(mid, n):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def findNum(self, n: int):

		def check(p, n):
			temp = p
			f = 5
			count = 0
			while f <= p:
				count += temp // f
				f *= 5
			if count >= n:
				return True
			else:
				return False
		low = 0
		high = n * 5
		ans = 0
		while low <= high:
			mid = (low + high) // 2
			res = check(mid, n)
			if res == True:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


def zerocheck(a, n):
	zeroes = 0
	num = 1
	while num <= a:
		num = num * 5
		zeroes += a // num
	return zeroes >= n

class Solution:

	def findNum(self, n: int):
		if n == 1:
			return 5
		low = 5
		high = 5 * n
		while low != high:
			mid = (low + high) // 2
			if zerocheck(mid, n):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def zeros(self, num):
		count = 0
		while num:
			num //= 5
			count += num
		return count

	def findNum(self, n: int):
		if n == 0:
			return 0
		(l, r) = (5, 5 * n)
		while l < r:
			mid = (l + r) // 2
			if self.zeros(mid) >= n:
				r = mid
			else:
				l = mid + 1
		return l


class Solution:

	def findNum(self, n: int):
		low = 0
		high = n * 5
		ans = high
		while low <= high:
			mid = (low + high) // 2
			cnt = 0
			num = 5
			while mid // num != 0:
				cnt += mid // num
				num *= 5
			if cnt < n:
				low = mid + 1
			else:
				ans = min(ans, mid)
				high = mid - 1
		return ans


def count_trails(n):
	count = 0
	f = 5
	while f <= n:
		count += n // f
		f = f * 5
	return count

class Solution:

	def findNum(self, n: int):
		(s, e) = (0, 5 * n)
		while s <= e:
			mid = s + (e - s) // 2
			if count_trails(mid) >= n:
				e = mid - 1
			else:
				s = mid + 1
		return s


class Solution:

	def check(self, p, n):
		count = 0
		f = 5
		while f <= p:
			count += p // f
			f *= 5
		return count >= n

	def findNum(self, n: int):
		(l, r) = (0, 5 * n)
		while l < r:
			mid = (l + r) // 2
			if self.check(mid, n):
				r = mid
			else:
				l = mid + 1
		return l


class Solution:

	def isPossible(self, mid, n):
		tmp = 5
		cnt = 0
		while tmp <= mid:
			cnt += mid // tmp
			tmp = tmp * 5
		return cnt >= n

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


class Solution:

	def findNum(self, n: int):

		def ispossible(num, n):
			cnt = 0
			while num >= 5:
				cnt += num // 5
				num = num // 5
			if cnt >= n:
				return True
			return False
		if n == 1:
			return 5
		elif n == 0:
			return 0
		start = 6
		end = n * 5
		ans = 0
		while start <= end:
			mid = start + end >> 1
			if ispossible(mid, n):
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
		return ans


class Solution:

	def zeros_count(self, x):
		deno = 5
		zeros = 0
		while x >= deno:
			zeros += x // deno
			deno *= 5
		return zeros

	def findNum(self, n: int):
		low = 0
		high = n * 5
		ans = low
		while low <= high:
			mid = (low + high) // 2
			zero = self.zeros_count(mid)
			if zero >= n:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def trailingzeros(self, n):
		c = 0
		while n:
			n //= 5
			c += n
		return c

	def binarysearch(self, l, r, k):
		if l <= r:
			mid = (l + r) // 2
			t = self.trailingzeros(mid)
			if t >= k:
				return self.binarysearch(l, mid - 1, k)
			else:
				return self.binarysearch(mid + 1, r, k)
		return l

	def findNum(self, n: int):
		return self.binarysearch(0, 5 * n, n)


class Solution:

	def findNum(self, n: int):

		def count(m, n):
			f = 5
			c = 0
			while f <= m:
				c += m // f
				f = f * 5
			return c >= n
		if n == 1:
			return 5
		(l, h) = (0, 5 * n)
		while l < h:
			mid = l + h >> 1
			if count(mid, n):
				h = mid
			else:
				l = mid + 1
		return l


class Solution:

	def findNum(self, n: int):
		lo = 0
		hi = 10 ** 6
		ans = -1
		while lo <= hi:
			mi = (lo + hi) // 2
			if self.getZeroes(mi) >= n:
				ans = mi
				hi = mi - 1
			else:
				lo = mi + 1
		return ans

	def getZeroes(self, x):
		sm = 0
		while x // 5:
			sm += x // 5
			x = x // 5
		return sm


class Solution:

	def check(self, mid, n):
		temp = mid
		f = 5
		cnt = 0
		while f <= temp:
			cnt += temp // f
			f = f * 5
		return cnt >= n

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


class Solution:

	def findNum(self, n: int):

		def make(x):
			t = 0
			k = 5
			m = 1
			while x // k > 0:
				t += x // k
				m *= 2
				k *= 5
				if t >= n:
					return True
			return False
		(x, y) = (0, 2 ** 32)
		while x <= y:
			m = x + (y - x) // 2
			if not make(m):
				x = m + 1
			else:
				y = m - 1
		return x


class Solution:

	def findNum(self, n: int):
		(lo, hi) = (0, n * 5)
		ans = lo
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			if self.findTrailingZeros(mid) >= n:
				ans = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return ans

	def findTrailingZeros(self, x):
		mul = 5
		zeroes = 0
		while x >= mul:
			zeroes += x // mul
			mul *= 5
		return zeroes