Stepping Numbers

Example

Sample Input: n = 10, m = 50

Expected Output: [10, 12, 21, 23, 32, 34, 43, 45]

Recommended: Try to solve the problem yourself on Coding Ninjas Studio by clicking: Stepping Numbers. 

Approach 1: Brute Force

The first and easiest way to solve this problem is using Brute Force. In this approach, we just loop from n to m and for each number check if the number is a stepping number or not, and then print accordingly.

The step-by-step implementation of this approach is as follows:

1. Create a function (say printSteppingNos()) that takes n and m as arguments.
2. Run a loop i from n up to m. 
   1. For each i, check if it is a stepping number or not.
   2. If it is a stepping number, print it.
3. Create a function (say checkSteppingNos()) that takes a number num as an argument and checks if num is a stepping number or not.
4. To do so, declare a variable, prevDigit, and initialize it to -1.
5. Now loop while num is not zero.
   1. For each iteration, declare a variable, curDigit,  and set its value to (num%10).
   2. Check if prevDigit is -1 or not.
      1. If not -1 then, check if the absolute difference between currDigit and prevDigit is 1 or not.
         1. If not 1 then, return FALSE.
      2. If -1 then, set num to (num/10) and prevDigit to curDigit.
6. Once the while loop is exhausted, return TRUE. It means that num has passed all the above tests and is a stepping number.

Java implementation of Approach 1

public class SteppingStoneBruteForce {

  public static boolean checkSteppingNos(int num)
  {
      int prevDigit = -1;

      while (num > 0)
      {
          int curDigit = num % 10;

          if (prevDigit != -1)
          {
              if (Math.abs(curDigit-prevDigit) != 1)
                  return false;
          }
          num /= 10;
          prevDigit = curDigit;
      }
      return true;
  }

  public static void printSteppingNos(int start,int end)
  {
      System.out.print("The Stepping Numbers from " + start + " to " + end + " are: ");
      for (int i = start; i <= end; i++)
          if (checkSteppingNos(i))
              System.out.print(i+ " ");
  }

  public static void main(String[] args)
  {
      int n = 0, m = 32;

      printSteppingNos(n,m);
  }
}

OUTPUT

The Stepping Numbers from 0 to 32 are: 0 1 2 3 4 5 6 7 8 9 10 12 21 23 32 

Approach 2: DFS Traversal

This approach requires some knowledge about DFS Algorithm. In this approach, we use the fact that all the numbers between [0…9] are stepping numbers. So we loop from 0 to 9, create a graph, and perform DFS traversal.

The step-by-step explanation of this approach is as follows:

1. Create a function (say printSteppingNos()) that takes n and m as arguments.
2. Inside this function, create an array arr that will contain all the stepping numbers between n and m.
3. Loop i from 0 to 9.
   1. For each i, call DFSTraversal() and pass n, m, i, and arr as parameters.
4. Sort arr in ascending order and print it.  
5. Create a function (say DFSTraversal()) that takes start, end, steppingNum, and steppingNumList as arguments. This function will use recursion to create the graph and perform Depth First Search(DFS). 
6. The base case is if steppingNum is greater than or equal to start and less than or equal to end.
   1. If true, then add steppingNum to steppingNumList.
7. If steppingNum is equal to 0 or greater than end, then exit the function.
8. Declare a variable (say lastDigit) and set its value to (steppingNum%10) 
9. The two possible neighbours of lastDigit can be one more or one less than its tenth multiple. For that declare the following two variables:
   1. stepNumLeft and set its value to steppingNum*10 + (lastDigit - 1).
   2. stepNumRight  and set its value to steppingNum*10 + (lastDigit + 1).
10. Check if lastDigit is equal to zero or not. 
    1. If true, call DFSTraversal() with the values start, end, stepNumRight, steppingNumList. We do this because, logically, there is no positive left neighbour for the value zero. So, we simply call its right neighbour.
11. Else check if lastDigit is equal to nine or not.
    1. If true, call DFSTraversal() with the values start, end, stepNumLeft, steppingNumList. We do so because, logically, there is no single-digit  right neighbour for the value nine.
12. If the above two checks fail then,
    1. Call DFSTraversal() with the values start, end, stepNumLeft, steppingNumList.
    2. Call DFSTraversal() with the values start, end, stepNumRight, SteppingNumList.

Java Implementation of Approach 2

import java.util.*;

public class SteppingStoneDFS {

  public static void DFSTravel(int start,int end,int steppingNum, List<Integer> steppingNumList)
  {
      if (steppingNum >= start && steppingNum <= end)
          steppingNumList.add(steppingNum);

      if (steppingNum == 0 || steppingNum > end)
          return;

      int lastDigit = steppingNum % 10;

      int stepNumLeft = steppingNum*10 + (lastDigit-1);
      int stepNumRight = steppingNum*10 + (lastDigit+1);

      if (lastDigit == 0)
          DFSTravel(start, end, stepNumRight, steppingNumList);

      else if(lastDigit == 9)
          DFSTravel(start, end, stepNumLeft, steppingNumList);
      else
      {
          DFSTravel(start, end, stepNumLeft, steppingNumList);
          DFSTravel(start, end, stepNumRight, steppingNumList);
      }
  }

  public static void printSteppingNos(int start, int end)
  {
      List<Integer> steppingNumList = new ArrayList<>();
      System.out.print("The Stepping Numbers from " + start + " to " + end + " are: ");
      for (int i = 0 ; i <= 9 ; i++)
          DFSTravel(start, end, i, steppingNumList);

      Collections.sort(steppingNumList);
      System.out.println(steppingNumList);
  }

  public static void main(String[] args)
  {
      int n = 0, m = 32;

      printSteppingNos(n,m);
  }
}

OUTPUT

The Stepping Numbers from 0 to 32 are: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32]

Also check out Addition of Two Numbers in Java here.

Complexities

Time Complexity

In approach 1, we iterate throughout the given range [L, R] and, for each number, check if it is a stepping number or not. Thus the time complexity comes out to be,

T(n) = O((R-L+1)*log10R),

where R-L+1 is the total count of numbers in the range [L, R] and for each number, the complexity of checking if it is a stepping number is at most log10R because we iterate over all the digits of a number to check if it is stepping number or not. And a number in the range [L, R] can have at most log10R digits.

In approach 2, the DFS operation takes constant time, but sorting takes (N log N) time. Thus the time complexity comes out to be, 

T(n) = O(N log N),

where N is the number of stepping numbers within the range. 

Space Complexity

In approach 1, no extra space is required to carry out all the operations. Thus, 

Space Complexity = O(1).

In approach 2, we create an array of size N to store all stepping numbers. Thus,

Space Complexity = O(N),

where N is the number of stepping numbers within the range.

Frequently Asked Questions

1. What do mean by “Stepping Numbers”?
   A number is called a Stepping Number if the absolute difference between all the consecutive digits is 1. For example, 123 and 321 are Stepping Numbers; 145 and 982 are not Stepping Numbers.
   
    
2. Are there better solutions for the given problem?
   There is one more solution that can be considered better than DFS, and that is by using Breadth First Search(BFS). By applying BFS, we can avoid the time used in sorting the array due to which the overall time complexity becomes O(1). 

Key Takeaways

To summarize the article, we learned what stepping numbers are and how to find stepping numbers in a given range. We saw the problem statement, an example, and the two approaches. We also saw their Java implementations and discussed the time and space complexity. To sum up our article, we discussed a few FAQs.

Want to improve your coding skills? Start practicing problems of various difficulty levels on our Coding Ninjas Studio.

You can also read about - Strong number in c

Want to learn about topics like Web Technologies, Programing Fundamentals, Aptitude, DSA, and much more? Visit CN Library | Free Online Coding Resources today.

Happy Coding!