CODEWITHSUNDEEP
algorithm
Margo Eastham
Margo Eastham

Reputation: 655

Stepping Number program

I have the following problem:

The stepping number:

A number is called a stepping number if every adjacent digits, 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 = Integer.parseInt(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?

Upvotes: 1

Views: 5630

Answers (1)

hk6279
hk6279

Reputation: 1879

Instead of checking every number in [s,e], you can try printing every stepping number in [s,e].

It should looks like:

  1. Generate a list of 3-digit stepping number with value in [000,999]
  2. Create another list (for leftmost part before the comma) by add 1 to 9 into the new list and then add all element in list 1
  3. Find the smallest stepping number greater than or equal to s and check if the stepping number is in [s,e]
  4. Generate stepping numbers (by using list 1 and list 2) until the value is greater than e

Remark

List 1 holds 010 and 012, but exclude value start with 0 but not 01 like 045 (even 45 itself is a valid value)

s and/or e smaller than or equal to 2-digit value might need to handle specially.

Upvotes: 2

Related Questions