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: interview

Starter code:

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

Solutions:
class Solution:
     # def canTransform(self, start, end):
     #     """
     #     :type start: str
     #     :type end: str
     #     :rtype: bool
     #     """
 
     def canTransform(self, start, end):
         # For (i, x) and (j, y) in enumerate(start), enumerate(end)
         # where x != 'X' and y != 'X',
         # and where if one exhausts early, it's elements are (None, None),...
         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 not solid or accessible, return False
             if x != y or (x == 'L' and i < j) or (x == 'R' and i > j):
                 return False
 
         return True
         
         
         # 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):
         """
         :type start: str
         :type end: str
         :rtype: bool
         """
         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):
         """
         :type start: str
         :type end: str
         :rtype: bool
         """
         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):
         """
         :type start: str
         :type end: str
         :rtype: bool
         """
         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):
         """
         :type start: str
         :type end: str
         :rtype: bool
         """
         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):
         """
         :type start: str
         :type end: str
         :rtype: bool
         """
         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):
         """
         :type start: str
         :type end: str
         :rtype: bool
         """
         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):
         """
         :type start: str
         :type end: str
         :rtype: bool
         """
         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):
         """
         :type start: str
         :type end: str
         :rtype: bool
         """
         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):
         """
         :type start: str
         :type end: str
         :rtype: bool
         """
         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):
         """
         :type start: str
         :type end: str
         :rtype: bool
         """
         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):
         """
         :type start: str
         :type end: str
         :rtype: bool
         """
         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):
         """
         :type start: str
         :type end: str
         :rtype: bool
         """
         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))])