मान लीजिए हमारे पास दो पूर्णांक low और high हैं, हमें रेंज [low, high] में सभी स्टेपिंग नंबरों की एक सॉर्ट की गई सूची ढूंढनी और दिखानी है। एक स्टेपिंग नंबर एक पूर्णांक है जिसके सभी आसन्न अंकों का निरपेक्ष अंतर ठीक 1 होता है। उदाहरण के लिए, 321 एक स्टेपिंग नंबर है लेकिन 421 नहीं। यदि low=0 और high=21 है, तो परिणाम [0,1,2,3,4,5,6,7,8,9,10,12,21] होगा।
हल करने के चरण
- एक सरणी temp बनाएं
- solve() नामक एक विधि बनाएं, जो high, seed और len लेती है। len प्रारंभ में 0 है
- यदि seed > high, तो वापस लौटें
- seed को temp सरणी में डालें
- यदि seed 0 है, तो
- i को 1 से 9 तक लूप करें, solve(high, i, 1) करें
- अन्यथा
- lastDigit := seed % 10
- यदि lastDigit >= 1 और len+1 <= 10, तो solve(high, (seed*10) + lastDigit-1, len+1)
- यदि lastDigit <= 8 और len+1 <= 10, तो solve(high, (seed*10) + lastDigit+1, len+1)
- मुख्य विधि:
- solve(high, 0, 0) कॉल करें
- temp सरणी को सॉर्ट करें
- एक सरणी ans बनाएं
- i को 0 से temp आकार-1 तक लूप करें
- यदि temp[i] >= low, तो temp[i] को ans में डालें
- ans वापस करें
उदाहरण
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } typedef long long int lli; class Solution { public: vector <lli> temp; void solve(int high,lli seed=0, int len =0){ if(seed>high){ return; } temp.push_back(seed); if(!seed){ for(int i =1;i<=9;i++){ solve(high,i,1); } } else { int lastDigit = seed%10; if(lastDigit>=1 && len+1<=10) solve(high, (seed*10) + lastDigit-1,len+1); if(lastDigit<=8 && len+1<=10) solve(high, (seed*10) + lastDigit+1,len+1); } } vector<int> countSteppingNumbers(int low, int high) { solve(high); sort(temp.begin(),temp.end()); vector <int> ans; for(int i =0;i<temp.size();i++){ if(temp[i]>=low)ans.push_back(temp[i]); } return ans; } }; main(){ Solution ob; print_vector(ob.countSteppingNumbers(0,40)); }इनपुट
0 40
आउटपुट
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32, 34, ]