Stepping Numbers - dfs graph

stepping_number.cpp

#include<bits/stdc++.h>
using namespace std;

void dfs(vector<vector<int>> &adj,int arr[],int len,int curr,int curr_len,string temp){
    temp+=to_string(curr);
    if(curr_len == len){
        //cout<<temp<<" ";
        arr[stoi(temp)]=1;
        return;
    }
    for(int i=0;i<adj[curr].size();i++){
        dfs(adj,arr,len,adj[curr][i],curr_len+1,temp);
    }
}

int main()
 {
     vector<vector<int>> adj(10);
     for(int i=0;i<10;i++){
         for(int j=0;j<10;j++){
             if(abs(i-j)==1)
                adj[i].push_back(j);
         }
     }
     
     int arr[1000001];
     memset(arr,0,sizeof(arr));
     for(int i=1;i<7;i++){
         for(int j=0;j<10;j++){
             string temp ="";
             dfs(adj,arr,i,j,1,temp);
         }
     }
     for(int i=1;i<1000001;i++){
         arr[i] += arr[i-1];
     }
     int t;
	 cin>>t;
	 while(t--){
	    int n,m;
	    cin>>n>>m;
	    if(n==0){
	        cout<<arr[m]<<"\n";
	    }else
	        cout<<arr[m]-arr[n-1]<<"\n";
	 }
	 return 0;
}

A number is called stepping number if all adjacent digits have an absolute difference of 1, e.g. '321' is a Stepping Number while 421 is not. Given two integers n and m, find the count of all the stepping numbers in the range [n, m].

Input : n = 0, m = 21
Output : 13
Stepping no's are 0 1 2 3 4 5 6 7 8 9 10 12 21

This can be solved by creating a graph like,
0-1-2-3-4-5-6-7-8-9
Now let If we run dfs for length 3, from let nodes 3 will give the end result as 321,323,345,343. These all are steeping numbers. Thus running for length 1 to 6 and for all nodes will give all the steeping numbers. We can perform precomputation for the given range of numbers and solve query in constant time.