Given n, find count of n digit Stepping numbers. A number is called stepping number if all adjacent digits have an absolute difference of 1. 321 is a Stepping Number while 421 is not.
Examples :
Input : 2 Output : 17 Explanation: The numbers are 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98. Input : 1 Output : 10 Explanation: the numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
A naive approach is to run a loop for all n digit numbers and check for every number if it is Stepping.
An efficient approach is to use dynamic programming.
In dp[i][j], i denotes number of
digits and j denotes last digit.
// If there is only one digit
if (i == 1)
dp(i, j) = 1;
// If last digit is 0.
if (j == 0)
dp(i, j) = dp(i-1, j+1)
// If last digit is 9
else if (j == 9)
dp(i, j) = dp(i-1, j-1)
// If last digit is neither 0
// nor 9.
else
dp(i, j) = dp(i-1, j-1) +
dp(i-1, j+1)
Result is ?dp(n, j) where j varies
from 1 to 9.
C++
// CPP program to calculate the number of// n digit stepping numbers.#include <bits/stdc++.h>using namespace std;// function that calculates the answerlong long answer(int n){ // dp[i][j] stores count of i digit // stepping numbers ending with digit // j. int dp[n + 1][10]; // if n is 1 then answer will be 10. if (n == 1) return 10; // Initialize values for count of // digits equal to 1. for (int j = 0; j <= 9; j++) dp[1][j] = 1; // Compute values for count of digits // more than 1. for (int i = 2; i <= n; i++) { for (int j = 0; j <= 9; j++) { // If ending digit is 0 if (j == 0) dp[i][j] = dp[i - 1][j + 1]; // If ending digit is 9 else if (j == 9) dp[i][j] = dp[i - 1][j - 1]; // For other digits. else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]; } } // stores the final answer long long sum = 0; for (int j = 1; j <= 9; j++) sum += dp[n][j]; return sum;}// driver program to test the above functionint main(){ int n = 2; cout << answer(n); return 0;} |
Java
// Java program to calculate the number of// n digit stepping numbers.class GFG { // function that calculates the answer static long answer(int n) { // dp[i][j] stores count of i // digit stepping numbers ending // with digit j. int dp[][] = new int[n+1][10]; // if n is 1 then answer will be 10. if (n == 1) return 10; // Initialize values for count of // digits equal to 1. for (int j = 0; j <= 9; j++) dp[1][j] = 1; // Compute values for count of // digits more than 1. for (int i = 2; i <= n; i++) { for (int j = 0; j <= 9; j++) { // If ending digit is 0 if (j == 0) dp[i][j] = dp[i - 1][j + 1]; // If ending digit is 9 else if (j == 9) dp[i][j] = dp[i - 1][j - 1]; // For other digits. else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]; } } // stores the final answer long sum = 0; for (int j = 1; j <= 9; j++) sum += dp[n][j]; return sum; } // driver program to test the above function public static void main(String args[]) { int n = 2; System.out.println(answer(n)); }}/*This code is contributed by Nikita tiwari.*/ |
Python3
# Python3 program to calculate # the number of n digit# stepping numbers.# function that calculates# the answerdef answer(n): # dp[i][j] stores count of # i digit stepping numbers # ending with digit j. dp = [[0 for x in range(10)] for y in range(n + 1)]; # if n is 1 then answer # will be 10. if (n == 1): return 10; for j in range(10): dp[1][j] = 1; # Compute values for count # of digits more than 1. for i in range(2, n + 1): for j in range(10): # If ending digit is 0 if (j == 0): dp[i][j] = dp[i - 1][j + 1]; # If ending digit is 9 elif (j == 9): dp[i][j] = dp[i - 1][j - 1]; # For other digits. else: dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]); # stores the final answer sum = 0; for j in range(1, 10): sum = sum + dp[n][j]; return sum;# Driver Coden = 2;print(answer(n));# This code is contributed # by mits |
C#
// C# program to calculate the number of// n digit stepping numbers.using System;class GFG { // function that calculates the answer static long answer(int n) { // dp[i][j] stores count of i // digit stepping numbers ending // with digit j. int [,]dp = new int[n+1,10]; // if n is 1 then answer will be 10. if (n == 1) return 10; // Initialize values for count of // digits equal to 1. for (int j = 0; j <= 9; j++) dp[1,j] = 1; // Compute values for count of // digits more than 1. for (int i = 2; i <= n; i++) { for (int j = 0; j <= 9; j++) { // If ending digit is 0 if (j == 0) dp[i,j] = dp[i - 1,j + 1]; // If ending digit is 9 else if (j == 9) dp[i,j] = dp[i - 1,j - 1]; // For other digits. else dp[i,j] = dp[i - 1,j - 1] + dp[i - 1,j + 1]; } } // stores the final answer long sum = 0; for (int j = 1; j <= 9; j++) sum += dp[n,j]; return sum; } // driver program to test the above function public static void Main() { int n = 2; Console.WriteLine(answer(n)); }}/*This code is contributed by vt_m.*/ |
PHP
<?php// PHP program to calculate // the number of n digit// stepping numbers.// function that calculates// the answerfunction answer($n){ // dp[i][j] stores count of // i digit stepping numbers // ending with digit j. // if n is 1 then answer // will be 10. if ($n == 1) return 10; for ( $j = 0; $j <= 9; $j++) $dp[1][$j] = 1; // Compute values for count // of digits more than 1. for ($i = 2; $i <= $n; $i++) { for ($j = 0; $j <= 9; $j++) { // If ending digit is 0 if ($j == 0) $dp[$i][$j] = $dp[$i - 1][$j + 1]; // If ending digit is 9 else if ($j == 9) $dp[$i][$j] = $dp[$i - 1][$j - 1]; // For other digits. else $dp[$i][$j] = $dp[$i - 1][$j - 1] + $dp[$i - 1][$j + 1]; } } // stores the final answer $sum = 0; for ($j = 1; $j <= 9; $j++) $sum += $dp[$n][$j]; return $sum;}// Driver Code$n = 2;echo answer($n);// This code is contributed by aj_36?> |
Javascript
<script>// JavaScript program to calculate the number of// n digit stepping numbers.// Function that calculates the answerfunction answer(n){ // dp[i][j] stores count of i // digit stepping numbers ending // with digit j. let dp = new Array(n + 1); // Loop to create 2D array using 1D array for(var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } // If n is 1 then answer will be 10. if (n == 1) return 10; // Initialize values for count of // digits equal to 1. for(let j = 0; j <= 9; j++) dp[1][j] = 1; // Compute values for count of // digits more than 1. for(let i = 2; i <= n; i++) { for(let j = 0; j <= 9; j++) { // If ending digit is 0 if (j == 0) dp[i][j] = dp[i - 1][j + 1]; // If ending digit is 9 else if (j == 9) dp[i][j] = dp[i - 1][j - 1]; // For other digits. else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]; } } // Stores the final answer let sum = 0; for(let j = 1; j <= 9; j++) sum += dp[n][j]; return sum;} // Driver Codelet n = 2;document.write(answer(n));// This code is contributed by code_hunt </script> |
Output
17
Time Complexity: O(n), as we are using a loop to traverse n times and within each iteration there are 10 cases. So a total of 10*N that is equivalent to n.
Auxiliary Space: O(n), as we are using extra space of 10*n for dp array.
Efficient approach: Space optimization
In the previous approach, the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector dp of size 10 and initialize it with 1.
- Set a base case.
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- Create a variable sum and and update it by iterating over DP.
- At last return and print the final answer stored in sum .
Implementation:
C++
// CPP program to calculate the number of// n digit stepping numbers.#include <bits/stdc++.h>using namespace std;// function that calculates the answerlong long answer(int n){ // dp[i] stores count of i digit // stepping numbers ending with digits // 0 to 9. vector<long long> dp(10, 1); // if n is 1 then answer will be 10. if (n == 1) return 10; // Compute values for count of digits // more than 1. for (int i = 2; i <= n; i++) { vector<long long> new_dp(10, 0); // If ending digit is 0 new_dp[0] = dp[1]; // If ending digit is 9 new_dp[9] = dp[8]; // For other digits. for (int j = 1; j <= 8; j++) new_dp[j] = dp[j - 1] + dp[j + 1]; dp = new_dp; } // stores the final answer long long sum = 0; for (int j = 1; j <= 9; j++) sum += dp[j]; return sum;}// driver program to test the above functionint main(){ int n = 2; cout << answer(n); return 0;} |
Java
import java.util.*;public class Main{ // function that calculates the answer static long answer(int n) { // dp[i] stores count of i digit // stepping numbers ending with digits // 0 to 9. ArrayList<Long> dp = new ArrayList<>(Collections.nCopies(10, 1L)); // if n is 1 then answer will be 10. if (n == 1) return 10; // Compute values for count of digits // more than 1. for (int i = 2; i <= n; i++) { ArrayList<Long> new_dp = new ArrayList<>(Collections.nCopies(10, 0L)); // If ending digit is 0 new_dp.set(0, dp.get(1)); // If ending digit is 9 new_dp.set(9, dp.get(8)); // For other digits. for (int j = 1; j <= 8; j++) new_dp.set(j, dp.get(j - 1) + dp.get(j + 1)); dp = new_dp; } // stores the final answer long sum = 0; for (int j = 1; j <= 9; j++) sum += dp.get(j); return sum; } // driver program to test the above function public static void main(String[] args) { int n = 2; System.out.println(answer(n)); }}// This code is contributed by Prajwal Kandekar |
Python3
def answer(n): # dp[i] stores count of i digit # stepping numbers ending with digits # 0 to 9. dp = [1] * 10 # if n is 1 then answer will be 10. if n == 1: return 10 # Compute values for count of digits # more than 1. for i in range(2, n + 1): new_dp = [0] * 10 # If ending digit is 0 new_dp[0] = dp[1] # If ending digit is 9 new_dp[9] = dp[8] # For other digits. for j in range(1, 9): new_dp[j] = dp[j - 1] + dp[j + 1] dp = new_dp # stores the final answer sum = 0 for j in range(1, 10): sum += dp[j] return sum# driver program to test the above functionn = 2print(answer(n)) |
C#
using System;using System.Collections.Generic;class SteppingNumbers { // function that calculates the answer static long Answer(int n) { // dp[i] stores count of i digit // stepping numbers ending with digits // 0 to 9. List<long> dp = new List<long>(); for (int i = 0; i < 10; i++) { dp.Add(1); } // if n is 1 then answer will be 10. if (n == 1) { return 10; } // Compute values for count of digits // more than 1. for (int i = 2; i <= n; i++) { List<long> new_dp = new List<long>(); for (int j = 0; j < 10; j++) { new_dp.Add(0); } // If ending digit is 0 new_dp[0] = dp[1]; // If ending digit is 9 new_dp[9] = dp[8]; // For other digits. for (int j = 1; j <= 8; j++) { new_dp[j] = dp[j - 1] + dp[j + 1]; } dp = new_dp; } // stores the final answer long sum = 0; for (int j = 1; j <= 9; j++) { sum += dp[j]; } return sum; } // driver program to test the above function static void Main() { int n = 2; Console.WriteLine(Answer(n)); }} |
Javascript
function answer(n) { // dp[i] stores count of i digit // stepping numbers ending with digits // 0 to 9. let dp = new Array(10).fill(1); // if n is 1 then answer will be 10. if (n == 1) return 10; // Compute values for count of digits // more than 1. for (let i = 2; i <= n; i++) { let new_dp = new Array(10).fill(0); // If ending digit is 0 new_dp[0] = dp[1]; // If ending digit is 9 new_dp[9] = dp[8]; // For other digits. for (let j = 1; j <= 8; j++) new_dp[j] = dp[j - 1] + dp[j + 1]; dp = new_dp; } // stores the final answer let sum = 0; for (let j = 1; j <= 9; j++) sum += dp[j]; return sum;}// driver program to test the above functionlet n = 2;console.log(answer(n)); |
Output
17
Time complexity: O(n)
Auxiliary Space: O(10) => O(1)
Number of n digit stepping numbers | Space optimized solution
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!