[low, high] পরিসরে সব স্টেপিং নম্বর বের করতে হবে। স্টেপিং নম্বর = প্রতিটি আডজেসেন্ট ডিজিটের পার্থক্য ঠিক ১।
উদাহরণ: low=0, high=21 → [0,1,2,3,4,5,6,7,8,9,10,12,21]।
সমাধানের ধাপসমূহ
- BFS/DFS দিয়ে সব স্টেপিং নম্বর জেনারেট করুন।
- সিড ০ থেকে শুরু করে ১-৯ ট্রাই করুন।
- প্রতিটি নম্বরের লাস্ট ডিজিট থেকে ±১ করে নতুন নম্বর বানান।
- লেন্থ ১০-এর বেশি হলে বন্ধ করুন (int লিমিট)।
- জেনারেট করা নম্বরগুলো সাজিয়ে [low, high] ফিল্টার করুন।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<long long> v) {
cout << "[";
for (auto x : v) cout << x << ", ";
cout << "]" << endl;
}
class Solution {
vector<long long> temp;
void solve(long long high, long long seed = 0, int len = 0) {
if (seed > high) return;
temp.push_back(seed);
if (seed == 0) {
for (int i = 1; i <= 9; i++) solve(high, i, 1);
} else {
int last = seed % 10;
if (last >= 1 && len + 1 <= 10) solve(high, seed * 10 + last - 1, len + 1);
if (last <= 8 && len + 1 <= 10) solve(high, seed * 10 + last + 1, len + 1);
}
}
public:
vector<int> countSteppingNumbers(int low, int high) {
solve(high);
sort(temp.begin(), temp.end());
vector<int> ans;
for (auto x : temp) if (x >= low) ans.push_back(x);
return ans;
}
};
int 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, ]
