Stepping Number Solution Optimization

Question

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 <= e) {
        String str = String.valueOf(s);
        if(isSteppingNumber(str)) System.out.print(str + " ");
        s++;
    }
}

public boolean isSteppingNumber(String str) {
    if(str.length() == 1) return false; // 1-digit number can't be a stepping number

    List<String> 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?

Answer 1

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<String> 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 <= end ) {
        if ( isSteppingNumber(start) ) {
            System.out.print(start + " ");
        }

        start++;
    }
}

private static boolean isSteppingNumber(int number) {
    if ( number < BASE ) {
        return false;
    }

    while ( number > 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.

Answer 2

Well, there aren't that many stepping numbers between 10 and 989. You can hard-code them all into your program. Then, just chunk up the numbers into groups of three digits and run through the pre-generated lists. That is the approach that would give you the fastest run-time performance, I think.

Answer 3

As far as I understand it:

• your function should not ever deal with strings; it should deal with integer types
• it should iterate with an outer loop that quits if the number reaches zero
• in an inner loop that executes three times (due to the "comma" rule), it should use the modulus (% 10) to get the current digit, do the step check with the previous digit (whose value is stored outside of the loop), return false out of the function if the check fails, and otherwise divide the number by 10.

An example (in Python; I don't have access to a Java env):

def is_stepping(x):
    if x < 10:
        return False
    while True:
        prev = x % 10
        for i in range(2):
            x = int(x/10)
            if x == 0:
                return True
            cur = x % 10
            if abs(prev - cur) != 1:
                return False
            prev = cur
        x = int(x/10)