Number of n-digit stepping numbers in C++

11 Feb 2025 | 4 min read

In this article, we will discuss how to find numbers of n-digit stepping numbers in C++. Before going to its program, we must know about the Stepping Numbers.

What are Stepping Numbers?

Stepping numbers are the numbers whose adjacent digits are arranged in such a way there is a single difference between them all. For instance, in 567, every successive difference of 1 exists between the neighboring numbers (5, 6, 7)

In this case, we will be given the number N, and our task is to count all N-digit stepping numbers.

Example 1:

Input:

Output:

Explanation:

210, 123, 321, 456, 234, 345, 432, 454, 543, 567, 657, 678, 765, 789, 876, 987, 989.

Example 2:

Input:

Output:

Explanation:

3210, 1234, 2345, 3456, 4567, 5678, 6789, 7654, 8765, 9876.

Using several C++ approaches, we will determine the maximum number of n-digit numbers that are also stepping numbers. We will also talk about the best solution in terms of space optimization.

Approach 1: Iteration Method:

In order to determine whether a number is a stepping number or not, we first develop a function called steppingNumber. Since it is a Boolean function, the result is either true or false.
Using to_string() function, we change the number to a string in this method. After that, the difference between each digit is determined by iterating over all of the digits. It is untrue if the difference is not 1. If not, the outcome is accurate.
The function to count the stepping numbers is created. We iterate from the first N-digit number to the last N-digit number in this function. We use the steppingNumber function for every number. The count value is increased by 1 if in case the function returns true.

Example:

Let us take an example to illustrate the stepping numbers in C++.

Output:

Number of n-digit stepping numbers in C++

Approach 2: Space Optimized Search:

The count of N-digit stepping numbers and (N - 1) digit stepping numbers are stored in two arrays.
The loop is executed from 2 to N. Because numbers can fall between 0 and 9, we execute two loops within this loop, each going from 0 to 9. We use the data from the currentCount array to update the value of the previousCount array for each digit.
The value of previousCount[x- 1] is added to the currentCount array if (x > 0). This is because if the first digit of the (N - 1)th digit is equal to (ex- 1), adding one to it yields the N digit stepping number.
The value of previousCount[x + 1] is added to the currentCount array if (x< 9). This is so that, if the first digit equals (x + 1), adding one to the first digit of the (N - 1)th digit yields the N-digit stepping number.
The array currentCount's values are then added together.