A number is called stepping number if all adjacent digits have an absolute difference of 1. For example, 321 is a stepping number while 421 is not.
Given an integer n, return the number of stepping numbers with n digits. Mod the result by 10 ** 9 + 7.
Constraints
n ≤ 100,000Example 1
Input
n = 2
Output
17
Explanation
The results include: [12, 23, 34, 45, 56, 67, 78, 89, 98, 87, 76, 65, 54, 43, 32, 21, 10]
Bruteforcing with Depth First Search Algorithm
We can bruteforcing with the DFS (Depth First Search Algorithm). Enumerate the next digits until we have n-size number. The time complexity is O(2^n) as for each digit, we have two possibilities.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class SteppingNumbers: def countSteppingNumbers(self, n): ans = 0 M = 1e9+7 if n == 1: return 10 @lru_cache(maxsize=None) def dfs(cur): nonlocal ans, n, M if len(str(cur)) == n: return 1 last = cur % 10 ans = 0 if last < 9: ans = (ans + dfs(cur * 10 + last + 1)) % M if last > 0: ans = (ans + dfs(cur * 10 + last - 1)) % M return ans for i in range(1, 10): ans = (ans + dfs(i)) % M return ans |
class SteppingNumbers:
def countSteppingNumbers(self, n):
ans = 0
M = 1e9+7
if n == 1:
return 10
@lru_cache(maxsize=None)
def dfs(cur):
nonlocal ans, n, M
if len(str(cur)) == n:
return 1
last = cur % 10
ans = 0
if last < 9:
ans = (ans + dfs(cur * 10 + last + 1)) % M
if last > 0:
ans = (ans + dfs(cur * 10 + last - 1)) % M
return ans
for i in range(1, 10):
ans = (ans + dfs(i)) % M
return ansTop-Down Dynamic Programming Algorithm (Recursion with Memoization) to Count Stepping Numbers
We can DFS on the last digit and the remaining digits left, then the complexity will be brought down to O(10*n) as we are using the Memoization via @lru_cache (Least Recently Used Cache).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class SteppingNumbers: def countSteppingNumbers(self, n): ans = 0 M = 1e9+7 if n == 1: return 10 @lru_cache(maxsize=None) def dfs(last, left): nonlocal ans, n, M if left == 0: return 1 ans = 0 if last < 9: ans = (ans + dfs(last + 1, left - 1)) % M if last > 0: ans = (ans + dfs(last - 1, left - 1)) % M return ans for i in range(1, 10): ans = (ans + dfs(i, n - 1)) % M return ans |
class SteppingNumbers:
def countSteppingNumbers(self, n):
ans = 0
M = 1e9+7
if n == 1:
return 10
@lru_cache(maxsize=None)
def dfs(last, left):
nonlocal ans, n, M
if left == 0:
return 1
ans = 0
if last < 9:
ans = (ans + dfs(last + 1, left - 1)) % M
if last > 0:
ans = (ans + dfs(last - 1, left - 1)) % M
return ans
for i in range(1, 10):
ans = (ans + dfs(i, n - 1)) % M
return ansWhen n is 1, we have to also accrue the ‘0’ – special case.
Space complexity is O(N) as we are relying on the LRU cache and the fact that it uses Recursion (implicit use of Stack).
Bottom-up Dynamic Programming Algorithm to Count the Stepping Numbers
We can iterately compute the Dynamic Programming equation (from Bottom-Up) – a bit similar to Fibonacci Numbers.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class SteppingNumbers: def countSteppingNumbers(self, n): # nums starting with (digit) if n == 0: return 0 if n == 1: return 10 dp = [1] * 10 for _ in range(n - 1): ndp = [0] * 10 ndp[0] = dp[1] for i in range(1, 9): ndp[i] = dp[i - 1] + dp[i + 1] ndp[9] = dp[8] dp = ndp return sum(dp[1:]) % (10 ** 9 + 7) |
class SteppingNumbers:
def countSteppingNumbers(self, n):
# nums starting with (digit)
if n == 0:
return 0
if n == 1:
return 10
dp = [1] * 10
for _ in range(n - 1):
ndp = [0] * 10
ndp[0] = dp[1]
for i in range(1, 9):
ndp[i] = dp[i - 1] + dp[i + 1]
ndp[9] = dp[8]
dp = ndp
return sum(dp[1:]) % (10 ** 9 + 7)And we use dp[] a constant static array to record the number of solutions given last digits are 0 to 10. Then we just need to sum them up to a final answer.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Add One to List
Next Post: Teaching Kids Programming - Algorithms to Check Integer Power of Three
