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 2 zeroes at the end. Given K, find how many 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.


Note:


       K will be an integer in the range [0, 10^9].

Difficulty: MEDIUM_HARD
Tags: Sorting

Mathematics
Skill types: Sorting

Starter code:
class Solution:
    def preimageSizeFZF(self, K: int) -> int:
        

Solutions:
class Solution:

	def canTransform(self, start, end):
		for ((i, x), (j, y)) in itertools.zip_longest(((i, x) for (i, x) in enumerate(start) if x != 'X'), ((j, y) for (j, y) in enumerate(end) if y != 'X'), fillvalue=(None, None)):
			if x != y or (x == 'L' and i < j) or (x == 'R' and i > j):
				return False
		return True


class Solution:

	def canTransform(self, start, end):
		if len(start) != len(end) or start.replace('X', '') != end.replace('X', ''):
			return False
		(l, ll, r, rr) = (0, 0, 0, 0)
		for i in range(len(start)):
			if start[i] == 'L':
				l += 1
			elif start[i] == 'R':
				r += 1
			if end[i] == 'L':
				ll += 1
			elif end[i] == 'R':
				rr += 1
			if l > ll or r < rr:
				return False
		return True


class Solution:

	def canTransform(self, start, end):
		start_pair = [(i, c) for (i, c) in enumerate(start) if c != 'X']
		end_pair = [(i, c) for (i, c) in enumerate(end) if c != 'X']
		if len(start_pair) != len(end_pair):
			return False
		for ((i_start, c_start), (i_end, c_end)) in zip(start_pair, end_pair):
			if c_start != c_end or (c_start == 'L' and i_start < i_end) or (c_start == 'R' and i_start > i_end):
				return False
		return True


class Solution:

	def canTransform(self, start, end):
		previous = {'L': 'X', 'X': 'R'}
		if len(start) != len(end):
			return False
		start = list(start)
		for i in range(len(start)):
			if start[i] == end[i]:
				continue
			elif end[i] == 'R':
				return False
			else:
				cur = end[i]
				if i == len(end) - 1:
					return False
				for j in range(i + 1, len(end)):
					if start[j] == cur:
						p = j
						while p > i:
							if start[p - 1] == previous[cur]:
								p -= 1
							else:
								return False
						start[j] = start[p]
						start[p] = cur
						break
		return True


class Solution:

	def canTransform(self, start, end):
		if len(start) != len(end):
			return False
		(r, l) = (0, 0)
		for i in range(len(start)):
			if start[i] == 'R':
				r += 1
			if end[i] == 'R':
				r -= 1
			if start[i] == 'L':
				l -= 1
			if end[i] == 'L':
				l += 1
			if r > 0 and l != 0 or r < 0:
				return False
			if l > 0 and r != 0 or l < 0:
				return False
		return l == 0 and r == 0


class Solution:

	def findNextChar(self, string, i, char):
		otherChar = 'R' if char == 'L' else 'L'
		for i in range(i, len(string)):
			if string[i] == otherChar:
				return None
			if string[i] == char:
				return i
		return None

	def canTransform(self, start, end):
		end_i = 0
		for i in range(len(start)):
			if start[i] != 'X':
				end_i = self.findNextChar(end, end_i, start[i])
				if end_i == None or (start[i] == 'L' and end_i > i) or (start[i] == 'R' and end_i < i):
					return False
				end_i += 1
		for end_i in range(end_i, len(end)):
			if end[end_i] != 'X':
				return False
		return True


class Solution:

	def canTransform(self, start, end):
		s = [(c, i) for (i, c) in enumerate(start) if c == 'L' or c == 'R']
		e = [(c, i) for (i, c) in enumerate(end) if c == 'L' or c == 'R']
		return len(s) == len(e) and all((c1 == c2 and (i1 >= i2 and c1 == 'L' or (i1 <= i2 and c1 == 'R')) for ((c1, i1), (c2, i2)) in zip(s, e)))


class Solution:

	def canTransform(self, start, end):
		if start.replace('X', '') != end.replace('X', ''):
			return False
		t = 0
		for i in range(len(start)):
			if start[i] == 'L':
				while end[t] != 'L':
					t += 1
				if i < t:
					return False
				t += 1
		t = 0
		for i in range(len(start)):
			if start[i] == 'R':
				while end[t] != 'R':
					t += 1
				if i > t:
					return False
				t += 1
		return True


class Solution:

	def canTransform(self, start, end):
		start_helper = []
		for i in range(len(start)):
			if start[i] == 'L' or start[i] == 'R':
				start_helper.append((start[i], i))
		end_helper = []
		for i in range(len(end)):
			if end[i] == 'L' or end[i] == 'R':
				end_helper.append((end[i], i))
		if len(start_helper) != len(end_helper):
			return False
		for i in range(len(start_helper)):
			if start_helper[i][0] != end_helper[i][0]:
				return False
			elif start_helper[i][0] == 'L' and start_helper[i][1] < end_helper[i][1]:
				return False
			elif start_helper[i][0] == 'R' and start_helper[i][1] > end_helper[i][1]:
				return False
		return True


class Solution:

	def canTransform(self, start, end):
		n = len(start)
		i = 0
		j = 0
		while i < n and j < n:
			while i < n and start[i] == 'X':
				i += 1
			while j < n and end[j] == 'X':
				j += 1
			if i == n and j == n:
				return True
			if i == n or j == n:
				return False
			if start[i] != end[j]:
				return False
			if start[i] == 'L' and i < j:
				return False
			if start[i] == 'R' and i > j:
				return False
			i += 1
			j += 1
		return True


class Solution:

	def canTransform(self, start, end):
		tmps = start.replace('X', '')
		tmpe = end.replace('X', '')
		if tmps != tmpe:
			return False
		(sa, ta) = ([], [])
		i = 0
		while i < len(start):
			if start[i] == 'L':
				sa.append(i)
			elif start[i] == 'R':
				sa.append(-i)
			if end[i] == 'L':
				ta.append(i)
			elif end[i] == 'R':
				ta.append(-i)
			i += 1
		i = 0
		while i < len(sa):
			if sa[i] < ta[i]:
				return False
			i += 1
		return True


class Solution:

	def canTransform(self, start, end):
		if start.replace('X', '') != end.replace('X', ''):
			return False
		import operator
		for (char, op) in (('L', operator.gt), ('R', operator.lt)):
			j = 0
			for (i, c) in enumerate(start):
				if c == char:
					while j < len(end):
						if end[j] == char and op(j, i):
							return False
						elif end[j] == char:
							j += 1
							break
						j += 1
		return True


class Solution:

	def canTransform(self, start, end):

		def countX(s, char='R'):
			if char == 'L':
				s = s[::-1]
			countX = 0
			ans = []
			for c in s:
				if c == char:
					ans.append(countX)
				elif c == 'X':
					countX += 1
			return ans
		startLR = ''.join((c for c in start if c != 'X'))
		endLR = ''.join((c for c in end if c != 'X'))
		(startR, startL) = (countX(start, 'R'), countX(start, 'L'))
		(endR, endL) = (countX(end, 'R'), countX(end, 'L'))
		return startLR == endLR and all([startR[i] <= endR[i] for i in range(len(startR))]) and all([startL[i] <= endL[i] for i in range(len(startL))])