algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

lexicographical-number.py (1086B)


      1 class Solution:
      2     def lexicalOrder(self, n: int) -> list[int]:
      3         # ideas:
      4             # sorting
      5                 # too slow
      6             # some sort of stateless traversal
      7                 # prior is something, what's next given prior and max?
      8                     # how?
      9                         # it's the last number with 0 added to the right side
     10                         # if this is too large, increment the final digit
     11                             # if that's too large, increment the digit to the left and drop rightmost?
     12         prior = 1
     13         res = [prior]
     14         for _ in range(0,n-1):
     15             if prior * 10 <= n:
     16                 res.append(prior*10)
     17                 prior *= 10
     18                 continue
     19             if prior + 1 <= n and (prior + 1) // 10 == prior // 10:
     20                 res.append(prior+1)
     21                 prior += 1
     22                 continue
     23             
     24             prior = prior // 10
     25             while (prior + 1) // 10 != prior // 10:
     26                 prior = prior // 10
     27 
     28             prior += 1
     29             res.append(prior)
     30         return res