fork download
copy 
  1. class Solution:
  2.  
  3.     def getCount(self, N):
  4.         if N == 0:
  5.             return 0
  6.  
  7.         # Predecessors for each digit (0-9)
  8.         predecessors = [
  9.             [0, 8],              # 0
  10.             [1, 2, 4],           # 1
  11.             [1, 2, 3, 5],        # 2
  12.             [2, 3, 6],           # 3
  13.             [1, 4, 5, 7],        # 4
  14.             [2, 4, 5, 6, 8],     # 5
  15.             [3, 5, 6, 9],        # 6
  16.             [4, 7, 8],           # 7
  17.             [0, 5, 7, 8, 9],     # 8
  18.             [6, 8, 9],           # 9
  19.         ]
  20.  
  21.         prev = [1] * 10  # For N=1, each digit has 1 way
  22.  
  23.         if N == 1:
  24.             return sum(prev)
  25.  
  26.         for _ in range(2, N + 1):
  27.             curr = [0] * 10
  28.             for d in range(10):
  29.                 curr[d] = sum(prev[x] for x in predecessors[d])
  30.             prev = curr
  31.  
  32.         return sum(prev)
  33.  
  34. # Example usage:
  35. # sol = Solution()
  36. # print(sol.getCount(2))  # Output: 36
Success #stdin #stdout 0.01s 7228KB
comments (?)
stdin
copy 
1
stdout
copy 
Standard output is empty
https://ideone.com/6D1M7v
language:
Python (cpython 2.7.16)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!