We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Knight Dialer

Number: 972

Difficulty: Medium

Paid? No

Companies: Google, Bloomberg, Amazon, Bridgewater Associates, TikTok

Problem Description

Given a standard phone keypad where only the numeric keys are allowed as starting positions, a chess knight makes valid L-shaped moves (two squares in one direction and one square perpendicular), and you must count the number of distinct phone numbers of length n that can be dialed. Each move must be a valid knight move and the answer should be returned modulo 10^9 + 7.

Key Insights

  • The knight's move is restricted by the keypad design, so precompute which digits can reach which others.
  • Dynamic Programming is applied where dp[i][j] represents the ways to reach digit j after i moves.
  • Only the numeric keys are valid positions, with digit 5 being isolated (no valid moves from it).
  • Use a rolling DP array (or update in-place) because the state at step i only depends on step i-1.
  • For each iteration, compute the cumulative number of dial sequences for each digit and take the modulo at each step.

Space and Time Complexity

Time Complexity: O(n) – For each move, a constant number of transitions (at most 3 per digit) are computed. Space Complexity: O(1) – Only a fixed size (10 elements) DP array is needed for computation.

Solution

We approach this problem using Dynamic Programming (DP). Start by defining a mapping for each digit that lists the reachable digits using valid knight moves on the keypad. Initialize a DP array with 10 entries, each set to 1, since starting from any digit constitutes a valid single-digit number. For each move (from 2 to n digits), compute a new DP array by summing counts from previous positions based on the knight move mapping. At each step, update using modulo 10^9 + 7 to handle large numbers. Finally, the sum of the entries in the DP array after n moves gives the total number of distinct phone numbers.

Code Solutions

# Python solution for Knight Dialer

MOD = 10**9 + 7

def knightDialer(n):
    # Mapping of each digit to all digits reachable by a knight moving on the keypad
    knight_moves = {
        0: [4, 6],
        1: [6, 8],
        2: [7, 9],
        3: [4, 8],
        4: [0, 3, 9],
        5: [],
        6: [0, 1, 7],
        7: [2, 6],
        8: [1, 3],
        9: [2, 4]
    }
    
    # Every digit is a valid starting point, initialize ways for length 1.
    dp = [1] * 10
    
    # Compute ways for each step from 2 to n.
    for _ in range(1, n):
        next_dp = [0] * 10
        # Update each digit based on possible knight moves
        for digit in range(10):
            for move in knight_moves[digit]:
                next_dp[move] = (next_dp[move] + dp[digit]) % MOD
        dp = next_dp  # Prepare for next iteration
    
    # Sum all possible ending positions
    return sum(dp) % MOD

# Example usage:
#print(knightDialer(1))  # Expected output: 10
#print(knightDialer(2))  # Expected output: 20
← Back to All Questions