Stepping Number Solution Optimization

I have the following problem:


The stepping number:


A number is called a stepping number if every adjacent digits, except those separated by commas, differ by 1. A stepping number can't be a 1-digit number, it must be at least a 2-digit number. For example, 45 and 8,343,545 are stepping numbers.
But, 890,098 is not. The difference between ‘9’ and ‘0’ should
not be considered as 1.


Given start number s and an end number e your function should list
out all the stepping numbers in the range including both the numbers s
& e.

My Attempt:

public void steppingNumber(int s, int e) {
    while(s  numbers = new ArrayList<>();

    while(str.length() >= 3) { // get every 3-digit comma-separated number
        numbers.add(str.substring(str.length()-3));
        str = str.substring(0,str.length()-3);
    }
    numbers.add(str); // Also get the last number left

    for(String num : numbers) { // for every 3-digit comma-separated number, check if it's a stepping number
        for(int i = 1; i < num.length(); i++) {
            int previousDigit = Character.getNumericValue(num.charAt(i-1));
            int currentDigit = Character.getNumericValue(num.charAt(i));

            if(Math.abs(previousDigit - currentDigit) != 1) return false;
        }
    }

    return true;
}

If the question were only to check if a number was a stepping number, I think my solution would be fine. However, if I should list all stepping numbers within the range, say 1 to 10^15, then my solution will run linear time, leave alone the checking part. Can anyone give a better solution for the given problem?

public void steppingNumber(int s, int e) {

As described in the problem statement, s is the starting number and e is the ending number. Why not call them start and end then? That way we don't have to refer to the problem statement to know what the variables mean.

I would also pick another name for the function. You are printing the stepping numbers, so call it printSteppingNumbers. As a general rule, functions should have verb names. They do things and their names should reflect that.

String str = String.valueOf(s);

Why a string? In C, this would make sense as the difference between a letter and a number in C is trivial (char is an integer type). Java isn't as forgiving. Even if you do want a string, this is the wrong place to do it. Call the function with s (or start).

if ( isSteppingNumber(start) ) {
        System.out.print(start + " ");
    }

I added braces ({}) around the then clause. This helps avoid a class of error where someone intends to add a new statement to the then clause but actually makes it run whether the if triggers or not. I also find it easier to read.

List numbers = new ArrayList<>();

while(str.length() >= 3) { // get every 3-digit comma-separated number
    numbers.add(str.substring(str.length()-3));
    str = str.substring(0,str.length()-3);
}

This seems overly complicated. You don't need to generate a List here. It's sufficient to check each chunk as you go through.

while ( str.length() > 3 ) {
    if ( ! isSteppingSequence(str.substring(str.length()-3)) ) {
        return false;
    }
    str = str.substring(0,str.length()-3);
}

return isSteppingSequence(str);

You also don't need >= here. A simple > is better, as you always want there to be one chunk left to test outside the loop.

But we can do better if we keep it as a number at this point. First, we need a constant.

private final static int CHUNK_SIZE = 1000;

Now we can use it.

while ( number > CHUNK_SIZE ) {
        if ( ! isSteppingSequence(number % CHUNK_SIZE) ) {
            return false;
        }

        number /= CHUNK_SIZE;
    }

    return isSteppingSequence(number);

Another constant.

private final static int BASE = 10;

Now we just need to define isSteppingSequence and we get:

private final static int BASE = 10;
private final static int CHUNK_SIZE = 1000;

private static void listSteppingNumbers(int start, int end) {
    while ( start  CHUNK_SIZE ) {
        if ( ! isSteppingSequence(number % CHUNK_SIZE) ) {
            return false;
        }

        number /= CHUNK_SIZE;
    }

    // all the other sequences were stepping, so 
    // if this one is, it's a valid stepping number
    // otherwise not
    return isSteppingSequence(number);
}

private static boolean isSteppingSequence(int number) {
    int previous_digit = number % BASE;
    number /= BASE;
    while ( number > 0 ) {
        int current_digit = number % BASE;

        if ( Math.abs(previous_digit - current_digit) != 1 ) {
            return false;
        }

        previous_digit = current_digit;
        number /= BASE;
    }

    // if number was less than BASE, then it skipped the while loop
    // and all single digit numbers are valid stepping sequences
    // so true
    // if it made it through the while loop, 
    // all the adjacent digits differed by 1
    // so true
    return true;
}

So we now have a more readable version of your initial algorithm. Since it doesn't convert to a String and from characters, I suspect that it will be slightly faster.

You also ask if we can do better than stepping through every number in the range and testing to see if it is a stepping number. Certainly we can. We can generate the stepping numbers by composition. We don't have to search for them. I notice that this is described in more detail on Stack Overflow.

StackExchange Code Review Q#74441, answer score: 2