Problem Statement:
You are given 2 values, low, high. You need to find the sequential digits, where one number is more than the previous digit.
You need to return the result in sorted order.
Example
Input: low = 100, high = 300 Output: [123,234]
Solution
We will use backtracking in the solution.
We need the integers from 1 to 9. We dont consider 0 as it is the smallest.
So for every digit from 1 to 10, we call the backtracking function that will check if there is a sequence number and if it is there, then it will put it in the result.
Solution in C++
#include<iostream> #include<vector> #include<algorithm> #include<string> #include<vector> #include<set> using namespace std; vector<int> res; void backtrack(int low,int high,int curr_num,int index) { if(curr_num>=low && curr_num<=high){ res.push_back(curr_num); } if(index == 10 || curr_num >= high) return; backtrack(low, high, curr_num*10+index, index+1); } vector<int> get_sequential_digits(int low, int high) { for(int i=1; i<10; i++) backtrack(low,high,0,i); sort(res.begin(),res.end()); return res; } int main() { get_sequential_digits(1000, 14000); cout<<"Result = "<<endl; for (int i = 0; i < res.size(); i++) { cout<<res[i]<<" "; } return 0; }
Output:
1234 2345 3456 4567 5678 6789 12345