Problem 178: Step Numbers

Mathematical Analysis

Dynamic Programming Approach

We define a DP state:

• dp[n][d][mask] = number of n-digit step numbers ending in digit d, where mask is a bitmask indicating which digits 0-9 have appeared.

Transitions

From state (n, d, mask), we can extend to:

• (n+1, d-1, mask | (1 << (d-1))) if d >= 1
• (n+1, d+1, mask | (1 << (d+1))) if d <= 8

Base Case

For n = 1: dp[1][d][1 << d] = 1 for d = 1, …, 9 (no leading zeros).

Answer

where $1023 = 2^{10} - 1$ represents all digits 0-9 being present.

Optimization

Since we need at least 10 digits (to include all 0-9), and each step changes by 1, we need at least 9 steps from 0 to 9. So the minimum number of digits is 10.

The mask has $2^{10} = 1024$ states, digits have 10 states, and length goes up to 40. Total states: $40 \times 10 \times 1024 = 409600$, which is very manageable.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Answer

Complexity

Time: $O(N \times D \times 2^D) = O(40 \times 10 \times 1024)$, essentially $O(1)$.

Space: $O(D \times 2^D)$ with rolling array optimization.

#include <bits/stdc++.h>
using namespace std;

// Problem 178: Step Numbers
// Count pandigital step numbers (containing all digits 0-9) with up to 40 digits.
// DP: dp[d][mask] = count of step numbers ending in digit d with digit set mask.

int main() {
    const int MAXN = 40;
    const int FULL = (1 << 10) - 1;  // 1023

    // dp[d][mask]
    long long dp[10][1024] = {};
    long long ndp[10][1024] = {};

    // Base case: 1-digit numbers (d = 1..9, no leading zero)
    for (int d = 1; d <= 9; d++) {
        dp[d][1 << d] = 1;
    }

    long long answer = 0;

    // Check if 1-digit numbers are pandigital (they can't be)
    for (int d = 0; d <= 9; d++) {
        answer += dp[d][FULL];
    }

    // Extend from length n to n+1
    for (int n = 1; n < MAXN; n++) {
        memset(ndp, 0, sizeof(ndp));
        for (int d = 0; d <= 9; d++) {
            for (int mask = 0; mask <= FULL; mask++) {
                if (dp[d][mask] == 0) continue;
                long long val = dp[d][mask];
                if (d >= 1) {
                    ndp[d-1][mask | (1 << (d-1))] += val;
                }
                if (d <= 8) {
                    ndp[d+1][mask | (1 << (d+1))] += val;
                }
            }
        }
        memcpy(dp, ndp, sizeof(dp));

        // Count pandigital step numbers of length n+1
        for (int d = 0; d <= 9; d++) {
            answer += dp[d][FULL];
        }
    }

    cout << answer << endl;
    return 0;
}

"""
Problem 178: Step Numbers

Count pandigital step numbers (containing all digits 0-9) with up to 40 digits.
DP approach with state (last_digit, digit_bitmask).
"""


def solve():

    MAXN = 40
    FULL = (1 << 10) - 1  # 1023 = all digits 0-9 present

    # dp[d][mask] = count of step numbers ending in digit d with digit set mask
    dp = [[0] * 1024 for _ in range(10)]

    # Base: 1-digit numbers (no leading zero)
    for d in range(1, 10):
        dp[d][1 << d] = 1

    answer = 0

    # Check 1-digit pandigital (impossible)
    for d in range(10):
        answer += dp[d][FULL]

    for n in range(1, MAXN):
        ndp = [[0] * 1024 for _ in range(10)]
        for d in range(10):
            for mask in range(1024):
                if dp[d][mask] == 0:
                    continue
                val = dp[d][mask]
                if d >= 1:
                    ndp[d-1][mask | (1 << (d-1))] += val
                if d <= 8:
                    ndp[d+1][mask | (1 << (d+1))] += val
        dp = ndp

        for d in range(10):
            answer += dp[d][FULL]

    return answer


answer = solve()
assert answer == 126461847755
print(answer)