Count N-Digit Stepping Numbers

Problem

Given an integer N, count how many N-digit "stepping" (crazy) numbers exist. A stepping number is an N-digit positive integer where the absolute difference between any two consecutive digits is 1. Leading zeros are not allowed (so N-digit numbers must start with 1..9).

For example: here is a list of all 2-digit crazy numbers:

12	23	34	45	56	67	78	89	10
21	32	43	54	65	76	87	98

The total number of 2-digit crazy numbers is 17.

Examples

Example 1

Input: N = 2
Output: 17
Explanation: Two-digit stepping numbers include 10, 12, 21, 23, 32, ... (total 17).

Example 2

Input: N = 3
Output: 32

Example 3

Input: N = 4
Output: 61

Large N example

Input: N = 40
Output: 924903595810

Solution

We present two approaches: (1) dynamic programming over the last digit (recommended for counting), and (2) generation using BFS/DFS (useful for enumeration).

Method 1 - Dynamic programming on last digit

Intuition

The three-digit stepping numbers are built directly from two-digit stepping numbers by appending one more digit. The new (third) digit must be either one greater or one less than the last digit of the two-digit number. Therefore, in general each two-digit stepping number produces exactly two three-digit stepping numbers — one by adding +1 and one by adding -1 to its last digit — except when the last digit is 9 (only -1 is valid) or 0 (only +1 is valid). This shows the problem decomposes: counts for length L+1 can be derived from counts for length L and the solution can be built incrementally.

Here are examples showing how some 2-digit stepping numbers expand to 3-digit numbers:

12 -> 121, 123
23 -> 232, 234
21 -> 210, 212
34 -> 343, 345
32 -> 321, 323
45 -> 454, 456
43 -> 432, 434
56 -> 565, 567
54 -> 543, 545
67 -> 676, 678
65 -> 654, 656
78 -> 787, 789
76 -> 765, 767
89 -> 898
87 -> 876, 878
10 -> 101
98 -> 987, 989

Let us write down the count of stepping numbers that end in each digit (0 through 9). The small table below lists, for each ending digit, how many 2-digit and 3-digit stepping numbers end with that digit.

End Digit	Count (2-digit)	Count (3-digit)
0	1	1
1	1	3
2	2	3
3	2	4
4	2	4
5	2	4
6	2	4
7	2	4
8	2	3
9	1	2

Only one two-digit stepping number ends with 0 (that is 10). Only one two-digit number ends with 1 (21). Two two-digit numbers end with 2 (12, 32), and so on.

As discussed above, each two-digit stepping number generally generates two three-digit stepping numbers by appending either +1 or -1 to the last digit — except when the last digit is 0 or 9, where only one extension is possible. For example:

A two-digit number ending with 1 produces one three-digit number ending with 0 and one ending with 2.
The single three-digit number ending with 0 comes from the two-digit number ending with 1.
The three-digit numbers ending with 1 are contributed by the two-digit numbers ending with 0 and 2, giving a total of 3.

Summing the counts across the digits for a given length gives the total number of stepping numbers of that length; this observation leads directly to the dynamic programming recurrence used below. Build an N×10 table (or iterate a length-by-length 10-element dp array) and sum the row for the final length to obtain the answer.

Approach

Initialize dp for length 1 as dp[0]=0 and dp[1..9]=1 (no leading zeros for full numbers).
For len from 2 to N:
- For each digit d in 0..9, compute next[d] = (d>0 ? dp[d-1] : 0) + (d<9 ? dp[d+1] : 0).
- Assign dp = next.
After N iterations the answer is sum(dp).

Edge cases:

If N == 1 and you count only N-digit positive integers, answer = 9 (digits 1..9).

Below is a concrete DP table for small lengths to show how the recurrence builds counts by last digit. The table rows are labeled by length L and columns show counts of stepping numbers ending in digit 0..9. The final column is the row sum (total count for that length).

L \ Last Digit	0	1	2	3	4	5	6	7	8	9	Sum
1	0	1	1	1	1	1	1	1	1	1	9
2	1	1	2	2	2	2	2	2	2	1	17
3	1	3	3	4	4	4	4	4	3	2	32

How to read this table:

Row L=1 lists single-digit counts: digits 1..9 each contribute 1, 0 is not allowed as a leading digit so its count is 0 and the row sum is 9.
Row L=2 follows by applying the recurrence: e.g., count for last digit 2 is contributions from previous 1 and 3, so dp2[2] = dp1[1] + dp1[3] = 1 + 1 = 2.
Row L=3 continues similarly; the row sum is the total number of 3-digit stepping numbers (32).

Code

C++

class Solution {
 public:
  long long countStepping(int N) {
    if (N <= 0) return 0;
    if (N == 1) return 9; // digits 1..9
    long long dp[10] = {0};
    for (int d = 1; d <= 9; ++d) dp[d] = 1;
    for (int len = 2; len <= N; ++len) {
      long long next[10] = {0};
      for (int d = 0; d <= 9; ++d) {
        if (d > 0) next[d] += dp[d - 1];
        if (d < 9) next[d] += dp[d + 1];
      }
      for (int d = 0; d <= 9; ++d) dp[d] = next[d];
    }
    long long ans = 0;
    for (int d = 0; d <= 9; ++d) ans += dp[d];
    return ans;
  }
};

Go

package main

func countStepping(N int) int64 {
    if N <= 0 { return 0 }
    if N == 1 { return 9 }
    var dp [10]int64
    for d := 1; d <= 9; d++ { dp[d] = 1 }
    for len := 2; len <= N; len++ {
        var next [10]int64
        for d := 0; d <= 9; d++ {
            if d > 0 { next[d] += dp[d-1] }
            if d < 9 { next[d] += dp[d+1] }
        }
        dp = next
    }
    var ans int64
    for d := 0; d <= 9; d++ { ans += dp[d] }
    return ans
}

Java

class Solution {
  public long countStepping(int N) {
    if (N <= 0) return 0;
    if (N == 1) return 9;
    long[] dp = new long[10];
    for (int d = 1; d <= 9; d++) dp[d] = 1;
    for (int len = 2; len <= N; len++) {
      long[] next = new long[10];
      for (int d = 0; d <= 9; d++) {
        if (d > 0) next[d] += dp[d - 1];
        if (d < 9) next[d] += dp[d + 1];
      }
      dp = next;
    }
    long ans = 0;
    for (long v : dp) ans += v;
    return ans;
  }
}

Python

class Solution:
    def count_stepping(self, N: int) -> int:
        if N <= 0:
            return 0
        if N == 1:
            return 9
        dp = [0] * 10
        for d in range(1, 10):
            dp[d] = 1
        for _ in range(2, N + 1):
            nxt = [0] * 10
            for d in range(10):
                if d > 0:
                    nxt[d] += dp[d - 1]
                if d < 9:
                    nxt[d] += dp[d + 1]
            dp = nxt
        return sum(dp)

Complexity

⏰ Time complexity: O(N) — each of the N iterations updates a fixed 10-element state.
🧺 Space complexity: O(1) — constant extra space (arrays of size 10).

Method 2 - BFS / DFS generation (enumerate stepping numbers)

Intuition

Start from digits 1..9 and append lastDigit ± 1 repeatedly; BFS/DFS enumerates candidates level-by-level.

Approach

Initialize a queue (or recursion) with starting digits 1..9.
While queue not empty: pop x; if len(x) == N increment counter; otherwise generate neighbors x*10 + lastDigit-1 and x*10 + lastDigit+1 when valid and push.
Handle lastDigit == 0 (only +1) and lastDigit == 9 (only -1).

Code

C++

#include <queue>

class Solution {
 public:
  long long countSteppingBFS(int N) {
    if (N <= 0) return 0;
    if (N == 1) return 9;
    std::queue<std::pair<long long,int>> q; // (value, length)
    for (int d = 1; d <= 9; ++d) q.push({d,1});
    long long ans = 0;
    while (!q.empty()) {
      auto p = q.front(); q.pop();
      long long v = p.first; int len = p.second;
      if (len == N) { ans++; continue; }
      int last = v % 10;
      if (last > 0) q.push({v*10 + (last-1), len+1});
      if (last < 9) q.push({v*10 + (last+1), len+1});
    }
    return ans;
  }
};

Go

package main

type pair struct{ v int64; l int }

func countSteppingBFS(N int) int64 {
    if N <= 0 { return 0 }
    if N == 1 { return 9 }
    q := []pair{}
    for d := 1; d <= 9; d++ { q = append(q, pair{int64(d),1}) }
    var ans int64
    for len(q) > 0 {
        p := q[0]; q = q[1:]
        if p.l == N { ans++; continue }
        last := p.v % 10
        if last > 0 { q = append(q, pair{p.v*10 + (last-1), p.l+1}) }
        if last < 9 { q = append(q, pair{p.v*10 + (last+1), p.l+1}) }
    }
    return ans
}

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
  public long countSteppingBFS(int N) {
    if (N <= 0) return 0;
    if (N == 1) return 9;
    Deque<long[]> q = new ArrayDeque<>(); // {value, length}
    for (int d = 1; d <= 9; d++) q.add(new long[]{d,1});
    long ans = 0;
    while (!q.isEmpty()) {
      long[] p = q.remove(); long v = p[0]; int len = (int)p[1];
      if (len == N) { ans++; continue; }
      int last = (int)(v % 10);
      if (last > 0) q.add(new long[]{v*10 + last - 1, len+1});
      if (last < 9) q.add(new long[]{v*10 + last + 1, len+1});
    }
    return ans;
  }
}

Python

from collections import deque

class Solution:
    def count_stepping_bfs(self, N: int) -> int:
        if N <= 0:
            return 0
        if N == 1:
            return 9
        q = deque([(d,1) for d in range(1,10)])
        ans = 0
        while q:
            v, l = q.popleft()
            if l == N:
                ans += 1
                continue
            last = v % 10
            if last > 0:
                q.append((v*10 + (last-1), l+1))
            if last < 9:
                q.append((v*10 + (last+1), l+1))
        return ans

Complexity

⏰ Time complexity: O(K) where K is the number of stepping numbers generated (exponential in N if enumerating).
🧺 Space complexity: O(K) for the queue/recursion stack.

Count N-Digit Stepping Numbers

Problem

Examples

Example 1

Example 2

Example 3

Large N example

Solution

Method 1 - Dynamic programming on last digit

Intuition

Approach

Code

C++

Go

Java

Python

Complexity

Method 2 - BFS / DFS generation (enumerate stepping numbers)

Intuition

Approach

Code

C++

Go

Java

Python

Complexity

Continue Practicing

Comments