Count Stepping Numbers in Range

Count Stepping Numbers in Range

What is this problem about?

The "Count Stepping Numbers in Range interview question" is a digit-based counting challenge. A "stepping number" is an integer where the absolute difference between any two adjacent digits is exactly 1. For example, 123, 432, and 565 are stepping numbers, but 124 is not. You are given two numeric strings, low and high, and need to count how many stepping numbers exist in the inclusive range [low, high].

Why is this asked in interviews?

Amazon ask the "Count Stepping Numbers coding problem" to test a candidate's ability to solve "Digit DP" problems. These are a special class of "Dynamic Programming interview pattern" tasks where you count numbers satisfying a property by building them digit by digit. It evaluates your mastery of state-based counting and handling large number ranges that exceed 64-bit integer limits.

Algorithmic pattern used

This problem is solved using Digit Dynamic Programming.

1. The Range Rule: count(low, high) = count(high) - count(low - 1).
2. DP State: dp(index, prev_digit, is_less, is_started)
   • index: Current digit position we are filling.
   • prev_digit: The digit placed at index-1.
   • is_less: Boolean indicating if we are already smaller than the prefix of the limit string.
   • is_started: Boolean indicating if we have placed any non-zero digits yet.
3. Transitions: At each position, iterate through possible digits $d$. If is_started is true, $d$ must satisfy $|d - prev\_digit| = 1$.
4. Memoization: Store results for each state to avoid redundant recursive calls.

Example explanation

Range [10, 20]

• Stepping numbers: 10 (diff 1), 12 (diff 1).
• 11 is not a stepping number (diff 0).
• 21 is out of range. Result: 2.

Common mistakes candidates make

• String subtraction: Trying to calculate low - 1 when low is a string of length 100. It's often easier to check if low itself is a stepping number and then use count(high) - count(low).
• Leading Zeros: Failing to handle the is_started flag correctly, which leads to incorrect stepping logic for numbers with fewer digits than the limit.
• State Space: Forgetting to include the "tight constraint" (is_less) in the DP table.

Interview preparation tip

Practice "Digit DP" templates. They are remarkably consistent: they almost always involve a recursive function that builds a number from left to right while tracking boundaries and properties. Once you master the template, "Hard" problems like this become much more approachable.