ধরি আমরা একটি ফাংশন ডিজাইন করতে চাই যা একটি রেঞ্জ (low এবং high) এর মধ্যে মোট কতটি স্ট্রোবোগ্রামেটিক নাম্বার আছে তা গণনা করে। স্ট্রোবোগ্রামেটিক নাম্বার হল এমন সংখ্যা যা ১৮০ ডিগ্রি ঘুরালে একই দেখায়।
উদাহরণস্বরূপ, low = "50", high = "100" হলে আউটপুট হবে 3 কারণ তিনটি ফলাফল আছে: 69, 88, এবং 96।
সমাধানের ধাপসমূহ
findStrobogrammatic(n)ফাংশন:- একটি অ্যারে
ret - যদি n অড্ড (n & 1): ret-এ "0", "1", "8" পুশ
- অন্যথায়: ret-এ খালি স্ট্রিং পুশ
- যখন n > 1: n -= 2
- একটি অ্যারে
temp - ret-এর প্রতিটি s জন্য:
- যদি n > 3: temp-এ "0"+s+"0" পুশ
- temp-এ "1"+s+"1", "8"+s+"8", "6"+s+"9", "9"+s+"6" পুশ
- ret := temp
- একটি অ্যারে
- ret ফেরত
- একটি অ্যারে
- মেইন মেথড:
- ret := 0
- i = low.size() থেকে high.size() পর্যন্ত:
- v := findStrobogrammatic(i)
- v-এর প্রতিটি স্ট্রিং জন্য:
- ret += (1 যদি v[j].length() > low.length() এবং high.length() > v[j].length())
- ret ফেরত
প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector findStrobogrammatic(int n) {
vector ret;
if (n & 1) {
ret.push_back("0");
ret.push_back("1");
ret.push_back("8");
} else {
ret.push_back("");
}
for (; n > 1; n -= 2) {
vector temp;
for (int i = 0; i < ret.size(); i++) {
string s = ret[i];
if (n > 3) {
temp.push_back("0" + s + "0");
}
temp.push_back("1" + s + "1");
temp.push_back("8" + s + "8");
temp.push_back("6" + s + "9");
temp.push_back("9" + s + "6");
}
ret = temp;
}
return ret;
}
bool compare(string a, string b) {
return a.size() == b.size() ? a >= b : a.size() > b.size();
}
int strobogrammaticInRange(string low, string high) {
int ret = 0;
vector v;
for (int i = low.size(); i <= high.size(); i++) {
v = findStrobogrammatic(i);
for (int j = 0; j < v.size(); j++) {
ret += compare(v[j], low) && compare(high, v[j]);
}
}
return ret;
}
};
int main() {
Solution ob;
cout << (ob.strobogrammaticInRange("50", "100"));
}
ইনপুট
"50", "100"
আউটপুট
3
