# 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 <= 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
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?

• Just a quick clarification, is there any importance to the use of comma, or is it used purely for formatting purposes, i.e. the thousands separator? – h.j.k. Dec 22 '14 at 4:00
• Great question! Commas are not needed when listing out stepping numbers within a given range. They are only used for explanation purposes – Margo Eastham Dec 22 '14 at 4:13
• I should have caught this earlier, but it turns out this is broken code: "String str = Integer.parseInt(s);" :( Can you please provide the correct, working code here? Anyways, for starters, why is the method performing on Strings when a primitive int/long value should suffice? Especially when the comma is 'only used for explanation purposes'. In that case, there is also no need for splitting the input into three digits. That's the slightly confusing part... – h.j.k. Dec 22 '14 at 5:40
• Are you looking for the Integer.toString() method, or the more complex java.text.NumberFormat classes? – h.j.k. Dec 22 '14 at 5:43
• I've changed my code above. It was supposed to be String.valueOf(s). I converted int to String because I wanted to access every digit, of a given number, at constant time. For example, if I had integer 345, I wouldn't be able to access 3, 4, or, 5 directly. Another way of doing this is using int array, so I can directly point to num[0], num[1], or num[2]. I hope that makes sense. – Margo Eastham Dec 22 '14 at 6:01

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
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.

• Thanks for explaining your optimization thoroughly! I thought it would be easier to truncate every 3-digit numbers from the back using String because it had a substring method. But, thanks, I'll try to keep in mind to use int to solve int problems next time. Your optimization definitely looks more elegant and easier to read! – Margo Eastham Dec 22 '14 at 19:08

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.

• You're absolutely right. I certainly can! Didn't think about it because I didn't realize there weren't many stepping numbers between [10,989] – Margo Eastham Dec 22 '14 at 19:14

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)

• Thank you! I will keep in mind to use int to solve int problems next time – Margo Eastham Dec 22 '14 at 19:16