Posted on by Kalkicode
Code Number

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

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

Categories
Relative Post