Counting Stepping Numbers of N Digits in Python: Top 5 Methods

Rate this post

πŸ’‘ Problem Formulation: A stepping number is a number where each digit is within 1 of its neighboring digits. The task is to create a program in Python that counts the number of stepping numbers that have exactly n digits. For example, given n = 2, the desired output would be 17 (the stepping numbers are 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98).

Method 1: Recursive Generation of Stepping Numbers

This method involves using a recursive function that generates stepping numbers by adding or subtracting one from the last digit of the current number until it reaches the desired length. This method is well-suited for smaller values of n due to its depth-first search nature.

Here’s an example:

def stepping_numbers(n, num=0, results=None):
    if results is None:
        results = set()
    if n == 0:
        results.add(num)
    else:
        last_digit = num % 10
        if num > 0:
            if last_digit  0:
                stepping_numbers(n - 1, num * 10 + last_digit - 1, results)
        else:
            for next_digit in range(1, 10):
                stepping_numbers(n - 1, next_digit, results)
    return len(results)

print(stepping_numbers(2))

Output: 17

This code snippet defines a recursive function stepping_numbers that builds and counts stepping numbers of n digits. It starts from single digits (unless num is initially 0) and builds up by appending a digit on the left which is one higher or lower than the last digit, until the length of the number matches n. The base case is when n reaches 0, at which point the number is added to the results set. When initially called with num as 0, the function enters the special for-loop to handle single-digit starting points.

Method 2: Dynamic Programming

This method uses dynamic programming to build a table that counts stepping numbers, constructively building up from smaller digit counts to the desired number of digits. It is efficient for larger n as it avoids the redundancy of recursive calls.

Here’s an example:

def count_stepping_numbers(n):
    dp = [[0] * 10 for _ in range(n+1)]
    for i in range(1, 10):
        dp[1][i] = 1
    for i in range(2, n+1):
        for j in range(10):
            if j > 0:
                dp[i][j] += dp[i-1][j-1]
            if j < 9:
                dp[i][j] += dp[i-1][j+1]
    return sum(dp[n])

print(count_stepping_numbers(2))

Output: 17

The code initializes a two-dimensional dp array where dp[i][j] represents the count of stepping numbers with i digits and ending in the digit j. It first populates the base case (single digit numbers) and then iteratively fills in the table based on the stepping number property. Finally, it sums up all counts for n digits to provide the answer.

Method 3: Breadth-First Search (BFS)

Breadth-first search is a graph traversal technique that can be used to iteratively generate stepping numbers of a given length. Starting with single-digit numbers, the algorithm appends possible next digits until reaching the desired length.

Here’s an example:

from collections import deque

def bfs_stepping_numbers(n):
    if n == 1:
        return 9
    queue = deque(range(1, 10))
    count = 0
    while queue:
        num = queue.popleft()
        if len(str(num)) == n:
            count += 1
        else:
            last_digit = num % 10
            if last_digit > 0:
                queue.append(num * 10 + last_digit - 1)
            if last_digit < 9:
                queue.append(num * 10 + last_digit + 1)
    return count

print(bfs_stepping_numbers(2))

Output: 17

This code snippet performs a breadth-first search to find all stepping numbers with n digits. Starting from a queue of all single-digit numbers, it extends each number by appending a digit that is one less or one more than the last digit of the current number until it reaches the desired length. Whenever a number with n digits is dequeued, the count is incremented.

Method 4: Iterative Generation with Queues

This method is similar to BFS but uses queue operations to generate numbers of the next length from numbers of the current length. It iteratively goes through each possible digit adding a next stepped digit and counting the results.

Here’s an example:

from collections import deque

def iterative_stepping_numbers(n):
    if n == 1: return 9
    current, next = deque(range(1, 10)), deque()
    for _ in range(n-1):
        while current:
            num = current.popleft()
            last_digit = num % 10
            if last_digit > 0: next.append(num*10 + last_digit - 1)
            if last_digit < 9: next.append(num*10 + last_digit + 1)
        current, next = next, deque()
    return len(current)
    
print(iterative_stepping_numbers(2))

Output: 17

The code defines a function iterative_stepping_numbers that uses two queues to generate stepping numbers of n digits in an iterative manner. Every element from the current queue is extended by adding a stepped digit to generate the stepping numbers of the next length, which are stored in the next queue. After each iteration, the current queue is updated with the contents of the next queue, which is then cleared.

Bonus One-Liner Method 5: Using List Comprehension

A compact, less efficient approach utilizing Python’s list comprehension feature combines a range operation with a filter that checks for the stepping number property. This method is computationally intensive and not recommended for large values of n.

Here’s an example:

def oneliner_stepping_numbers(n):
    return len([x for x in range(10**(n-1), 10**n) if all(abs(int(str(x)[i]) - int(str(x)[i+1])) == 1 for i in range(len(str(x)) - 1))])

print(oneliner_stepping_numbers(2))

Output: 17

The function oneliner_stepping_numbers uses a list comprehension to iterate over the range of numbers with n digits and filters out those that do not satisfy the stepping number property. It counts the length of the resulting list to return the number of stepping numbers of n digits. The stepping property is checked by pairwise comparing digits to confirm they differ by one.

Summary/Discussion

  • Method 1: Recursive Generation of Stepping Numbers. Strengths: Conceptually clear, simple implementation. Weaknesses: Computational overhead with recursion, not efficient for large n.
  • Method 2: Dynamic Programming. Strengths: Very efficient for larger n, avoids redundant calculations. Weaknesses: Slightly complex implementation, requires understanding of DP concepts.
  • Method 3: Breadth-First Search (BFS). Strengths: Iterative, faster than recursion for larger n. Weaknesses: Uses additional memory to store the queue, may be slower for very large n.
  • Method 4: Iterative Generation with Queues. Strengths: Simple iterative approach, memory-efficient compared to BFS. Weaknesses: Might not be as fast as dynamic programming for very large n.
  • Method 5: Using List Comprehension. Strengths: One-liner, clean syntax. Weaknesses: Inefficient, not practical for large n, and can be hard to understand.