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

1
2
3

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

Example 2

1
2

Input: N = 3
Output: 32

Example 3

1
2

Input: N = 4
Output: 61

Large N example

1
2

Input: N = 40
Output: 924903595810
Similar Problems

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#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;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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.