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
  &amp; e.


My Attempt:

public void steppingNumber(int s, int e) {
    while(s &lt;= 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&lt;String&gt; numbers = new ArrayList&lt;&gt;();

    while(str.length() &gt;= 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 &lt; 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&lt;String&gt; numbers = new ArrayList&lt;&gt;();

while(str.length() &gt;= 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() &gt; 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 &gt;= here.  A simple &gt; 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 &gt; 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 &lt;= end ) {
        if ( isSteppingNumber(start) ) {
            System.out.print(start + " ");
        }

        start++;
    }
}

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

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