Finding Stepping Numbers

So, stepping numbers are these cool numbers where the difference between adjacent digits is always one. Like, 10 and 12 are stepping numbers, but 23 is not (because 2 and 3 are fine, but if you had a 4, 3 and 4 aren’t stepping). And now, I’ve got this task where I need to find all those stepping numbers between X and Y.

First off, I’d probably want to check if X is greater than Y. If they are flipped, I could just say there are no stepping numbers in that case and stop right there. But if not, here’s what I think I should do!

I’ll consider creating a function that starts from each digit from 0 to 9 and then builds numbers by adding or subtracting 1 to the last digit. For example:

• Start from 0, then you can only build up to 1.
• Start from 1, and you can create 10 or 12 (because 0 and 2 are the only choices).
• Do this recursively until the number reaches Y.

Once I’ve got those numbers, I’d then check if they fall between X and Y and add them to my final list. Oh, and I need to keep them sorted. I guess that can be done naturally with the way I’m building them?

And if I hit some giant numbers like 10⁹, I’d have to be careful not to waste time checking every single number. Going digit by digit is probably way more efficient, right?

Here’s a quick pseudo-code I was thinking about:

function findSteppingNumbers(X, Y) {
    if (X > Y) return [];
    
    steppingNums = [];
    
    for (digit in 0 to 9) {
        findSteppingNumbersFrom(digit, X, Y, steppingNums);
    }

    return sort(steppingNums);
}

function findSteppingNumbersFrom(number, X, Y, steppingNums) {
    if (number != 0 && number >= X && number <= Y) {
        steppingNums.push(number);
    }

    lastDigit = number % 10;

    if (lastDigit > 0) {
        findSteppingNumbersFrom(number * 10 + (lastDigit - 1), X, Y, steppingNums);
    }
    if (lastDigit < 9) {
        findSteppingNumbersFrom(number * 10 + (lastDigit + 1), X, Y, steppingNums);
    }
}
    

I think this will help me get all the stepping numbers without going through every number in between! And if there are no stepping numbers found, that’s okay too. It’s just part of the challenge! Let’s go for it!