StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This can be done in O(log N). Consider the keypad and the possible moves on it as a graph <em>G(V, E)</em> where vertices are the available digits and edges say which digits can follow which. Now for each output position <em>i</em> we can form a vector <em>Paths(i)</em> containing the number of different paths each vertex can be reached in. Now it's pretty easy to see that for a given position <em>i</em> and digit <em>v</em>, the possible paths that it can be reached through is the sum of the different paths that possible preceding digits could be reached through, or <em>Paths(i)[v] = sum(Paths(i-1)[v2] * (1 if (v,v2) in E else 0) for v2 in V )</em>. Now, this is taking the sum of each position the preceding vector times a corresponding position in a column of the adjacency matrix. So we can simplify this as <em>Paths(i) = Paths(i-1) · A</em>, where <em>A</em> is the adjacency matrix of the graph. Getting rid of the recursion and taking advantage of associativity of matrix multiplication, this becomes <em>Paths(i) = Paths(1) · A^(i-1)</em>. We know <em>Paths(1)</em>: we have only one path, to the digit 1.</p> <p>The total number of paths for an n digit number is the sum of the paths for each digit, so the final algorithm becomes: <em>TotalPaths(n) = sum( [1,0,0,0,0,0,0,0,0,0] · A^(n-1) )</em></p> <p>The exponentiation can be calculated via squaring in <em>O(log(n))</em> time, given constant time multiplies, otherwise <em>O(M(n) * log(n))</em> where <em>M(n)</em> is the complexity of your favorite arbitrary precision multiplication algorithm for <em>n</em> digit numbers.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload