Generate 10-digit number using a phone keypad

Phone Keypad

10-digit Number

Number Generation

Mobile Keypad Input

Phone Number Creation

Generate 10-digit number using a phone keypad

Interview Questions practice on Codemia

Over 8,000 real interview questions from top companies, searchable by company and role.

Browse interview questions

Introduction

The "generate 10-digit numbers using a phone keypad" problem is a classic algorithm challenge: given a standard phone keypad and a starting digit, count or enumerate all 10-digit numbers where each successive digit is a valid knight's move (like chess) from the previous digit on the keypad. This is a dynamic programming problem that tests understanding of state transitions, memoization, and graph traversal.

Phone Keypad Layout

1+---+---+---+
2| 1 | 2 | 3 |
3+---+---+---+
4| 4 | 5 | 6 |
5+---+---+---+
6| 7 | 8 | 9 |
7+---+---+---+
8    | 0 |
9    +---+

Knight's Move Adjacency

From each digit, a knight (chess piece) can move to specific other digits:

python

1# Knight moves on a phone keypad
2moves = {
3    0: [4, 6],
4    1: [6, 8],
5    2: [7, 9],
6    3: [4, 8],
7    4: [0, 3, 9],
8    5: [],         # No valid knight moves from 5
9    6: [0, 1, 7],
10    7: [2, 6],
11    8: [1, 3],
12    9: [2, 4],
13}

Note: digit 5 has no valid knight moves (all destinations would fall off the keypad).

Solution 1: Recursive with Memoization

python

1from functools import lru_cache
2
3moves = {
4    0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8],
5    4: [0, 3, 9], 5: [], 6: [0, 1, 7],
6    7: [2, 6], 8: [1, 3], 9: [2, 4]
7}
8
9@lru_cache(maxsize=None)
10def count_numbers(digit, remaining):
11    """Count N-digit numbers starting from digit with remaining digits to place."""
12    if remaining == 0:
13        return 1
14
15    total = 0
16    for next_digit in moves[digit]:
17        total += count_numbers(next_digit, remaining - 1)
18    return total
19
20# Count all 10-digit numbers starting from each digit
21total = sum(count_numbers(d, 9) for d in range(10))
22print(f"Total 10-digit numbers: {total}")  # 1424

Solution 2: Dynamic Programming (Bottom-Up)

python

1def count_knight_numbers(n_digits):
2    moves = {
3        0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8],
4        4: [0, 3, 9], 5: [], 6: [0, 1, 7],
5        7: [2, 6], 8: [1, 3], 9: [2, 4]
6    }
7
8    # dp[digit] = number of sequences ending at this digit
9    dp = [1] * 10  # Base case: 1-digit numbers
10
11    for step in range(1, n_digits):
12        new_dp = [0] * 10
13        for digit in range(10):
14            for prev in moves[digit]:
15                new_dp[digit] += dp[prev]
16        dp = new_dp
17
18    return sum(dp)
19
20print(count_knight_numbers(10))  # 1424

Time complexity: O(N * 10) where N is the number of digits. Space complexity: O(10) = O(1).

Solution 3: Matrix Exponentiation

For very large N, use matrix exponentiation for O(log N) time:

python

1import numpy as np
2
3def count_knight_numbers_matrix(n_digits):
4    # Adjacency matrix for knight moves
5    adj = np.zeros((10, 10), dtype=np.int64)
6    moves = {
7        0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8],
8        4: [0, 3, 9], 5: [], 6: [0, 1, 7],
9        7: [2, 6], 8: [1, 3], 9: [2, 4]
10    }
11
12    for digit, targets in moves.items():
13        for target in targets:
14            adj[target][digit] = 1
15
16    # Matrix power gives count of paths of length n-1
17    result = np.linalg.matrix_power(adj, n_digits - 1)
18    return result.sum()
19
20print(count_knight_numbers_matrix(10))  # 1424

Solution 4: Enumerate All Numbers

To generate the actual numbers (feasible for small N):

python

1def generate_numbers(n_digits):
2    moves = {
3        0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8],
4        4: [0, 3, 9], 5: [], 6: [0, 1, 7],
5        7: [2, 6], 8: [1, 3], 9: [2, 4]
6    }
7
8    results = []
9
10    def backtrack(path):
11        if len(path) == n_digits:
12            results.append(''.join(map(str, path)))
13            return
14
15        current = path[-1]
16        for next_digit in moves[current]:
17            path.append(next_digit)
18            backtrack(path)
19            path.pop()
20
21    for start in range(10):
22        backtrack([start])
23
24    return results
25
26# Warning: grows exponentially — only feasible for small N
27numbers = generate_numbers(4)
28print(f"4-digit numbers: {len(numbers)}")
29print(numbers[:10])  # First 10 examples

Variations

Starting from a Specific Digit

python

# Count 10-digit numbers starting from digit 1 only
count = count_numbers(1, 9)
print(count)  # Varies by starting digit

Excluding Digit 0 and 5 (No Corner Pieces)

python

1# Only allow digits 1-9, skip 5
2restricted_moves = {
3    1: [6, 8], 2: [7, 9], 3: [4, 8],
4    4: [3, 9], 6: [1, 7],
5    7: [2, 6], 8: [1, 3], 9: [2, 4]
6}

Adjacent Moves (Not Knight)

A different variant uses adjacent digit moves instead of knight moves:

python

1adjacent = {
2    0: [8], 1: [2, 4], 2: [1, 3, 5], 3: [2, 6],
3    4: [1, 5, 7], 5: [2, 4, 6, 8], 6: [3, 5, 9],
4    7: [4, 8], 8: [5, 7, 9, 0], 9: [6, 8]
5}

Common Pitfalls

Forgetting digit 5 has no moves: In the knight variant, 5 cannot reach any other digit. Sequences that reach 5 terminate early, contributing 0 to the count.
Off-by-one in digit count: A 10-digit number has 9 transitions (moves), not 10. The DP loop runs n_digits - 1 times.
Integer overflow: For large N, counts grow exponentially. Use Python's arbitrary precision integers or modular arithmetic (% 10**9 + 7) in other languages.
Confusing knight vs adjacent moves: The classic problem uses knight moves (L-shaped, like chess), not simple adjacency. Verify which variant the problem asks for.
Starting digit 0: Some problem variants exclude 0 as a starting digit (phone numbers don't start with 0). Clarify the constraints.

Summary

The phone keypad knight problem counts N-digit numbers where each digit is a knight's move from the previous
Dynamic programming solves it in O(N) time with O(1) space using a 10-element array
Matrix exponentiation solves it in O(log N) for very large N
Digit 5 is a dead end (no valid knight moves)
Total 10-digit numbers: 1,424 (starting from any digit)

Free course

Beginner

7 lessons

2 hours

Tackling System Design Interview Problems

A short course that equips you with the skills to approach system design interviews methodically.

Start the free course

Interview Questions practice on Codemia

Over 8,000 real interview questions from top companies, searchable by company and role.

Browse interview questions