Skip to main content

Stepping Numbers

The Stepping Numbers problem is a classic mathematical challenge where we are required to find all the stepping numbers between two given integers (first and last). A stepping number is a number in which adjacent digits have a difference of 1. For example, 123 is a stepping number since |1-2|=1 and |2-3|=1. The goal is to implement a program that efficiently identifies and lists all the stepping numbers within the given range.

Explanation with Suitable Example

Let's take the range from -8 to 15 as an example. The program will first call the findSteppingNo() function with -8 as the first argument and 15 as the second argument. Since the second argument (15) is greater than the first argument (-8), the function proceeds with finding stepping numbers within this range.

The findSteppingNo() function will iterate through all the numbers from -8 to 15, and for each number, it will call the isStepping() function to determine if it is a stepping number. The isStepping() function checks if a number is a stepping number by comparing the difference between adjacent digits. If the difference is 1, it proceeds to the next pair of digits until all digits are checked.

In this example, the stepping numbers between -8 and 15 are: -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12

Pseudocode

function isStepping(number):
    if number is a single digit:
        return True

    n = absolute value of number
    digit1 = last digit of n
    n = n / 10

    while n is not 0:
        digit2 = last digit of n
        if the difference between digit2 and digit1 is 1:
            n = n / 10
            digit1 = digit2
        else:
            return False
    return True

function findSteppingNo(first, last):
    if last < first:
        swap first and last
    print "Stepping Numbers in", first, "to", last, "are:"
    for i from first to last:
        if isStepping(i):
            print i

Algorithm Explanation

  1. The isStepping() function first handles single-digit numbers, which are considered stepping numbers. It then extracts each digit of the given number, checks if the difference between adjacent digits is 1, and continues this process until all digits are checked. If all the differences are 1, the number is considered a stepping number and the function returns True.

  2. The findSteppingNo() function takes two arguments, first and last. If last is less than first, it swaps the two values to ensure a valid range. It then iterates from first to last, calling isStepping() for each number to identify stepping numbers. If a number is a stepping number, it is printed.

Program Solution

/*
  C program 
  Stepping Numbers
*/

#include <stdio.h>

// Check that number is stepping number
int isStepping(int number)
{
    if((number > -10 && number < 10))
    {
        // When number is single digit number
        return 1;
    }

    int n = number;

    if(n < 0)
    {
        n = - number;
    }
    // Get last digit
    int digit1 = n % 10;
    int digit2 = 0;

    n = n / 10;

    while(n != 0)
    {
        // Get last digit
        digit2 = n % 10;

        if(digit2+1 == digit1  || digit2-1 == digit1)
        {
            
            n = n / 10;

            digit1 = digit2;
        }
        else
        {
            return 0;
        }
    }
    return 1;
}

// This is handling request to find the Stepping number
void findSteppingNo(int first,int last)
{
    if(last < first)
    {
        // Change the order
        findSteppingNo(last,first);
    }
    else
    {
        printf("\n Stepping Number in %d to %d is \n",first,last);

        for (int i = first; i < last ; ++i)
        {
            if(isStepping(i)==1)
            {
                printf("  %d",i);
            }
        }
    }
    printf("\n");
}
int main() 
{ 

    //Test Case
    findSteppingNo(-8, 15);
    findSteppingNo(1, 50);
    return 0; 
}

Output

 Stepping Number in -8 to 15 is
  -8  -7  -6  -5  -4  -3  -2  -1  0  1  2  3  4  5  6  7  8  9  10  12

 Stepping Number in 1 to 50 is
  1  2  3  4  5  6  7  8  9  10  12  21  23  32  34  43  45
/*
  Java Program
  Stepping Numbers
*/
public class SteppingNumber
{
	// Check that number is stepping number
	public boolean isStepping(int number)
	{
		if ((number > -10 && number < 10))
		{
			// When number is single digit number
			return true;
		}
		int n = number;
		if (n < 0)
		{
			n = -number;
		}
		// Get last digit
		int digit1 = n % 10;
		int digit2 = 0;
		n = n / 10;
		while (n != 0)
		{
			// Get last digit
			digit2 = n % 10;
			if (digit2 + 1 == digit1 || digit2 - 1 == digit1)
			{
				n = n / 10;
				digit1 = digit2;
			}
			else
			{
				return false;
			}
		}
		return true;
	}
	// This is handling request to find the Stepping number
	public void findSteppingNo(int first, int last)
	{
		if (last < first)
		{
			// Change the order
			findSteppingNo(last, first);
		}
		else
		{
			System.out.print("\n Stepping Number in " + first + " to " + last + " is \n");
			for (int i = first; i < last; ++i)
			{
				if (isStepping(i) == true)
				{
					System.out.print("  " + i);
				}
			}
		}
		System.out.print("\n");
	}
	public static void main(String[] args)
	{
		SteppingNumber obj = new SteppingNumber();
		//Test Case
		obj.findSteppingNo(-8, 15);
		obj.findSteppingNo(1, 50);
	}
}

Output

 Stepping Number in -8 to 15 is
  -8  -7  -6  -5  -4  -3  -2  -1  0  1  2  3  4  5  6  7  8  9  10  12

 Stepping Number in 1 to 50 is
  1  2  3  4  5  6  7  8  9  10  12  21  23  32  34  43  45
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program
  Stepping Numbers
*/
class SteppingNumber
{
    public:
    //  Check that number is stepping number
    bool isStepping(int number)
    {
        if ((number > -10 && number < 10))
        {
            //  When number is single digit number
            return true;
        }
        int n = number;
        if (n < 0)
        {
            n = -number;
        }
        //  Get last digit
        int digit1 = n % 10;
        int digit2 = 0;
        n = n / 10;
        while (n != 0)
        {
            //  Get last digit
            digit2 = n % 10;
            if (digit2 + 1 == digit1 || digit2 - 1 == digit1)
            {
                n = n / 10;
                digit1 = digit2;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
    //  This is handling request to find the Stepping number
    void findSteppingNo(int first, int last)
    {
        if (last < first)
        {
            //  Change the order
            this->findSteppingNo(last, first);
        }
        else
        {
            cout << "\n Stepping Number in " << first << " to " << last << " is \n";
            for (int i = first; i < last; ++i)
            {
                if (this->isStepping(i) == true)
                {
                    cout << "  " << i;
                }
            }
        }
        cout << "\n";
    }
};
int main()
{
    SteppingNumber obj = SteppingNumber();
    // Test Case
    obj.findSteppingNo(-8, 15);
    obj.findSteppingNo(1, 50);
    return 0;
}

Output

 Stepping Number in -8 to 15 is
  -8  -7  -6  -5  -4  -3  -2  -1  0  1  2  3  4  5  6  7  8  9  10  12

 Stepping Number in 1 to 50 is
  1  2  3  4  5  6  7  8  9  10  12  21  23  32  34  43  45
// Include namespace system
using System;
/*
  C# Program
  Stepping Numbers
*/
public class SteppingNumber
{
	//  Check that number is stepping number
	public Boolean isStepping(int number)
	{
		if ((number > -10 && number < 10))
		{
			//  When number is single digit number
			return true;
		}
		int n = number;
		if (n < 0)
		{
			n = -number;
		}
		//  Get last digit
		int digit1 = n % 10;
		int digit2 = 0;
		n = n / 10;
		while (n != 0)
		{
			//  Get last digit
			digit2 = n % 10;
			if (digit2 + 1 == digit1 || digit2 - 1 == digit1)
			{
				n = n / 10;
				digit1 = digit2;
			}
			else
			{
				return false;
			}
		}
		return true;
	}
	//  This is handling request to find the Stepping number
	public void findSteppingNo(int first, int last)
	{
		if (last < first)
		{
			//  Change the order
			findSteppingNo(last, first);
		}
		else
		{
			Console.Write("\n Stepping Number in " + first + " to " + last + " is \n");
			for (int i = first; i < last; ++i)
			{
				if (isStepping(i) == true)
				{
					Console.Write("  " + i);
				}
			}
		}
		Console.Write("\n");
	}
	public static void Main(String[] args)
	{
		SteppingNumber obj = new SteppingNumber();
		// Test Case
		obj.findSteppingNo(-8, 15);
		obj.findSteppingNo(1, 50);
	}
}

Output

 Stepping Number in -8 to 15 is
  -8  -7  -6  -5  -4  -3  -2  -1  0  1  2  3  4  5  6  7  8  9  10  12

 Stepping Number in 1 to 50 is
  1  2  3  4  5  6  7  8  9  10  12  21  23  32  34  43  45
<?php
/*
  Php Program
  Stepping Numbers
*/
class SteppingNumber
{
	//  Check that number is stepping number
	public function isStepping($number)
	{
		if (($number > -10 && $number < 10))
		{
			//  When number is single digit number
			return true;
		}
		$n = $number;
		if ($n < 0)
		{
			$n = -$number;
		}
		//  Get last digit
		$digit1 = $n % 10;
		$digit2 = 0;
		$n = intval($n / 10);
		while ($n != 0)
		{
			//  Get last digit
			$digit2 = $n % 10;
			if ($digit2 + 1 == $digit1 || $digit2 - 1 == $digit1)
			{
				$n = intval($n / 10);
				$digit1 = $digit2;
			}
			else
			{
				return false;
			}
		}
		return true;
	}
	//  This is handling request to find the Stepping number
	public	function findSteppingNo($first, $last)
	{
		if ($last < $first)
		{
			//  Change the order
			$this->findSteppingNo($last, $first);
		}
		else
		{
			echo "\n Stepping Number in ". $first ." to ". $last ." is \n";
			for ($i = $first; $i < $last; ++$i)
			{
				if ($this->isStepping($i) == true)
				{
					echo "  ". $i;
				}
			}
		}
		echo "\n";
	}
}

function main()
{
	$obj = new SteppingNumber();
	// Test Case
	$obj->findSteppingNo(-8, 15);
	$obj->findSteppingNo(1, 50);
}
main();

Output

 Stepping Number in -8 to 15 is
  -8  -7  -6  -5  -4  -3  -2  -1  0  1  2  3  4  5  6  7  8  9  10  12

 Stepping Number in 1 to 50 is
  1  2  3  4  5  6  7  8  9  10  12  21  23  32  34  43  45
/*
  Node Js Program
  Stepping Numbers
*/
class SteppingNumber
{
	//  Check that number is stepping number
	isStepping(number)
	{
		if ((number > -10 && number < 10))
		{
			//  When number is single digit number
			return true;
		}
		var n = number;
		if (n < 0)
		{
			n = -number;
		}
		//  Get last digit
		var digit1 = n % 10;
		var digit2 = 0;
		n = parseInt(n / 10);
		while (n != 0)
		{
			//  Get last digit
			digit2 = n % 10;
			if (digit2 + 1 == digit1 || digit2 - 1 == digit1)
			{
				n = parseInt(n / 10);
				digit1 = digit2;
			}
			else
			{
				return false;
			}
		}
		return true;
	}
	//  This is handling request to find the Stepping number
	findSteppingNo(first, last)
	{
		if (last < first)
		{
			//  Change the order
			this.findSteppingNo(last, first);
		}
		else
		{
			process.stdout.write("\n Stepping Number in " + first + " to " + last + " is \n");
			for (var i = first; i < last; ++i)
			{
				if (this.isStepping(i) == true)
				{
					process.stdout.write("  " + i);
				}
			}
		}
		process.stdout.write("\n");
	}
}

function main()
{
	var obj = new SteppingNumber();
	// Test Case
	obj.findSteppingNo(-8, 15);
	obj.findSteppingNo(1, 50);
}
main();

Output

 Stepping Number in -8 to 15 is
  -8  -7  -6  -5  -4  -3  -2  -1  0  1  2  3  4  5  6  7  8  9  10  12

 Stepping Number in 1 to 50 is
  1  2  3  4  5  6  7  8  9  10  12  21  23  32  34  43  45
#   Python 3 Program
#   Stepping Numbers

class SteppingNumber :
	#   Check that number is stepping number
	def isStepping(self, number) :
		if ((number > -10 and number < 10)) :
			#   When number is single digit number
			return True
		
		n = number
		if (n < 0) :
			n = -number
		
		#   Get last digit
		digit1 = n % 10
		digit2 = 0
		n = int(n / 10)
		while (n != 0) :
			#   Get last digit
			digit2 = n % 10
			if (digit2 + 1 == digit1 or digit2 - 1 == digit1) :
				n = int(n / 10)
				digit1 = digit2
			else :
				return False
			
		
		return True
	
	#   This is handling request to find the Stepping number
	def findSteppingNo(self, first, last) :
		if (last < first) :
			#   Change the order
			self.findSteppingNo(last, first)
		else :
			print("\n Stepping Number in ", first ," to ", last ," is ")
			i = first
			while (i < last) :
				if (self.isStepping(i) == True) :
					print("  ", i, end = "")
				
				i += 1
			
		
		print(end = "\n")
	

def main() :
	obj = SteppingNumber()
	#  Test Case
	obj.findSteppingNo(-8, 15)
	obj.findSteppingNo(1, 50)

if __name__ == "__main__": main()

Output

 Stepping Number in  -8  to  15  is
   -8   -7   -6   -5   -4   -3   -2   -1   0   1   2   3   4   5   6   7   8   9   10   12

 Stepping Number in  1  to  50  is
   1   2   3   4   5   6   7   8   9   10   12   21   23   32   34   43   45
#   Ruby Program
#   Stepping Numbers

class SteppingNumber 
	#   Check that number is stepping number
	def isStepping(number) 
		if ((number > -10 && number < 10)) 
			#   When number is single digit number
			return true
		end

		n = number
		if (n < 0) 
			n = -number
		end

		#   Get last digit
		digit1 = n % 10
		digit2 = 0
		n = n / 10
		while (n != 0) 
			#   Get last digit
			digit2 = n % 10
			if (digit2 + 1 == digit1 || digit2 - 1 == digit1) 
				n = n / 10
				digit1 = digit2
			else 
				return false
			end

		end

		return true
	end

	#   This is handling request to find the Stepping number
	def findSteppingNo(first, last) 
		if (last < first) 
			#   Change the order
			self.findSteppingNo(last, first)
		else 
			print("\n Stepping Number in ", first ," to ", last ," is \n")
			i = first
			while (i < last) 
				if (self.isStepping(i) == true) 
					print("  ", i)
				end

				i += 1
			end

		end

		print("\n")
	end

end

def main() 
	obj = SteppingNumber.new()
	#  Test Case
	obj.findSteppingNo(-8, 15)
	obj.findSteppingNo(1, 50)
end

main()

Output

 Stepping Number in -8 to 15 is 
  -8  -7  -6  -5  -4  -3  -2  -1  0  1  2  3  4  5  6  7  8  9  10  12

 Stepping Number in 1 to 50 is 
  1  2  3  4  5  6  7  8  9  10  12  21  23  32  34  43  45

/*
  Scala Program
  Stepping Numbers
*/
class SteppingNumber
{
	//   Check that number is stepping number
	def isStepping(number: Int): Boolean = {
		if ((number > -10 && number < 10))
		{
			//   When number is single digit number
			return true;
		}
		var n: Int = number;
		if (n < 0)
		{
			n = -number;
		}
		//   Get last digit
		var digit1: Int = n % 10;
		var digit2: Int = 0;
		n = (n / 10).toInt;
		while (n != 0)
		{
			//   Get last digit
			digit2 = n % 10;
			if (digit2 + 1 == digit1 || digit2 - 1 == digit1)
			{
				n = (n / 10).toInt;
				digit1 = digit2;
			}
			else
			{
				return false;
			}
		}
		return true;
	}
	//   This is handling request to find the Stepping number
	def findSteppingNo(first: Int, last: Int): Unit = {
		if (last < first)
		{
			//   Change the order
			this.findSteppingNo(last, first);
		}
		else
		{
			print("\n Stepping Number in " + first + " to " + last + " is \n");
			var i: Int = first;
			while (i < last)
			{
				if (this.isStepping(i) == true)
				{
					print("  " + i);
				}
				i += 1;
			}
		}
		print("\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: SteppingNumber = new SteppingNumber();
		//  Test Case
		obj.findSteppingNo(-8, 15);
		obj.findSteppingNo(1, 50);
	}
}

Output

 Stepping Number in -8 to 15 is
  -8  -7  -6  -5  -4  -3  -2  -1  0  1  2  3  4  5  6  7  8  9  10  12

 Stepping Number in 1 to 50 is
  1  2  3  4  5  6  7  8  9  10  12  21  23  32  34  43  45
/*
  Swift 4 Program
  Stepping Numbers
*/
class SteppingNumber
{
	//   Check that number is stepping number
	func isStepping(_ number: Int)->Bool
	{
		if ((number > -10 && number < 10))
		{
			//   When number is single digit number
			return true;
		}
		var n: Int = number;
		if (n < 0)
		{
			n = -number;
		}
		//   Get last digit
		var digit1: Int = n % 10;
		var digit2: Int = 0;
		n = n / 10;
		while (n != 0)
		{
			//   Get last digit
			digit2 = n % 10;
			if (digit2 + 1 == digit1 || digit2 - 1 == digit1)
			{
				n = n / 10;
				digit1 = digit2;
			}
			else
			{
				return false;
			}
		}
		return true;
	}
	//   This is handling request to find the Stepping number
	func findSteppingNo(_ first: Int, _ last: Int)
	{
		if (last < first)
		{
			//   Change the order
			self.findSteppingNo(last, first);
		}
		else
		{
			print("\n Stepping Number in ", first ," to ", last ," is ");
			var i: Int = first;
			while (i < last)
			{
				if (self.isStepping(i) == true)
				{
					print("  ", i, terminator: "");
				}
				i += 1;
			}
		}
		print(terminator: "\n");
	}
}
func main()
{
	let obj: SteppingNumber = SteppingNumber();
	//  Test Case
	obj.findSteppingNo(-8, 15);
	obj.findSteppingNo(1, 50);
}
main();

Output

 Stepping Number in  -8  to  15  is
   -8   -7   -6   -5   -4   -3   -2   -1   0   1   2   3   4   5   6   7   8   9   10   12

 Stepping Number in  1  to  50  is
   1   2   3   4   5   6   7   8   9   10   12   21   23   32   34   43   45
/*
  Kotlin Program
  Stepping Numbers
*/
class SteppingNumber
{
	//   Check that number is stepping number
	fun isStepping(number: Int): Boolean
	{
		if ((number > -10 && number < 10))
		{
			//   When number is single digit number
			return true;
		}
		var n: Int = number;
		if (n < 0)
		{
			n = -number;
		}
		//   Get last digit
		var digit1: Int = n % 10;
		var digit2: Int ;
		n = n / 10;
		while (n != 0)
		{
			//   Get last digit
			digit2 = n % 10;
			if (digit2 + 1 == digit1 || digit2 - 1 == digit1)
			{
				n = n / 10;
				digit1 = digit2;
			}
			else
			{
				return false;
			}
		}
		return true;
	}
	//   This is handling request to find the Stepping number
	fun findSteppingNo(first: Int, last: Int): Unit
	{
		if (last < first)
		{
			//   Change the order
			this.findSteppingNo(last, first);
		}
		else
		{
			print("\n Stepping Number in " + first + " to " + last + " is \n");
			var i: Int = first;
			while (i < last)
			{
				if (this.isStepping(i) == true)
				{
					print("  " + i);
				}
				i += 1;
			}
		}
		print("\n");
	}
}
fun main(args: Array<String>): Unit
{
	var obj: SteppingNumber = SteppingNumber();
	//  Test Case
	obj.findSteppingNo(-8, 15);
	obj.findSteppingNo(1, 50);
}

Output

 Stepping Number in -8 to 15 is
  -8  -7  -6  -5  -4  -3  -2  -1  0  1  2  3  4  5  6  7  8  9  10  12

 Stepping Number in 1 to 50 is
  1  2  3  4  5  6  7  8  9  10  12  21  23  32  34  43  45
// Rust program 
// Stepping Numbers

fn main()
{
	//Test Case
	find_stepping_no(-8, 15);
	find_stepping_no(1, 50);
}

fn find_stepping_no(first: i32, last: i32)
{
	if last < first
	{
		// Change the order
		find_stepping_no(last, first);
	}
	else
	{
		print!("\n Stepping Number in {} to {} is \n", first, last);
		let mut i: i32 = first;
		while i < last
		{
			if is_stepping(i) == 1
			{
				print!("  {}", i);
			}
			i += 1;
		}
	}
	print!("\n");
}
fn is_stepping(number: i32) -> i32
{
	if  number > -10 && number < 10 
	{
		// When number is single digit number
		return 1;
	}
	let mut n: i32 = number;
	if n < 0
	{
		n = -number;
	}
	// Get last digit
	let mut digit1: i32 = n % 10;
	let mut digit2: i32  ;
	n = n / 10;
	while n != 0
	{
		// Get last digit
		digit2 = n % 10;
		if digit2 + 1 == digit1 || digit2 - 1 == digit1
		{
			n = n / 10;
			digit1 = digit2;
		}
		else
		{
			return 0;
		}
	}
	return 1;
}

Output

 Stepping Number in -8 to 15 is
  -8  -7  -6  -5  -4  -3  -2  -1  0  1  2  3  4  5  6  7  8  9  10  12

 Stepping Number in 1 to 50 is
  1  2  3  4  5  6  7  8  9  10  12  21  23  32  34  43  45

Output Explanation

For the test cases provided, the program produces the following output:

Stepping Number in -8 to 15 is
-8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 12

Stepping Number in 1 to 50 is
1 2 3 4 5 6 7 8 9 10 12 21 23 32 34 43 45

The first output shows the stepping numbers between -8 and 15, and the second output displays the stepping numbers between 1 and 50.

Time Complexity

The time complexity of the isStepping() function is O(log N), where N is the absolute value of the number. The function involves extracting each digit of the number, and the number of digits in N determines the number of iterations.

The time complexity of the findSteppingNo() function is O((M - N) * log M), where M is the greater of the two input numbers and N is the smaller. This is because the function iterates through all numbers in the given range and, for each number, checks if it is a stepping number using the isStepping() function.

Finally, the stepping numbers problem is efficiently solved with the provided C program, and the time complexity is reasonable for practical purposes.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment