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
-
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. -
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, callingisStepping()
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.
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