मान लीजिए हम एक फ़ंक्शन परिभाषित करना चाहते हैं जो (low और high) की सीमा में मौजूद कुल स्ट्रॉबोग्रामैटिक नंबरों की गिनती करे। जैसा कि हम जानते हैं कि एक स्ट्रॉबोग्रामैटिक नंबर वह संख्या है जो 180 डिग्री घुमाने पर समान दिखती है।
तो, यदि इनपुट low = "50", high = "100" है, तो आउटपुट 3 होगा क्योंकि तीन परिणाम हैं, 69, 88, और 96।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
findStrobogrammatic() नामक एक फ़ंक्शन परिभाषित करें, जो n लेगा,
एक ऐरे ret परिभाषित करें
यदि n & 1 शून्येतर है, तो −
"0" को ret के अंत में डालें
"1" को ret के अंत में डालें
"8" को ret के अंत में डालें
अन्यथा
खाली स्ट्रिंग को ret के अंत में डालें
n > 1 के लिए, n := n - 2 अद्यतन करें, करें −
एक ऐरे temp परिभाषित करें
i := 0 से आरंभ करें, जब i, ret के आकार से कम, अद्यतन करें (i को 1 से बढ़ाएं), करें −
s := ret[i]
यदि n > 3, तो −
"0" + s + "0" को temp के अंत में डालें
"1" + s + "1" को temp के अंत में डालें
"8" + s + "8" को temp के अंत में डालें
"6" + s + "9" को temp के अंत में डालें
"9" + s + "6" को temp के अंत में डालें
ret := temp
ret लौटाएं
मुख्य विधि से, निम्नलिखित करें −
ret := 0
एक ऐरे v परिभाषित करें
i := low के आकार से आरंभ करें, जब i <= high का आकार, अद्यतन करें (i को 1 से बढ़ाएं), करें −
v := findStrobogrammatic(i)
j := 0 से आरंभ करें, जब j, v के आकार से कम, अद्यतन करें (j को 1 से बढ़ाएं), करें −
ret := ret + (1 जब v[j] की लंबाई > low की लंबाई AND high की लंबाई > v[j] की लंबाई)
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
#include <bits/stdc++.h> using namespace std; class Solution { public: vector<string> findStrobogrammatic(int n) { vector<string> 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<string> 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<string> 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; } }; main(){ Solution ob; cout <<(ob.strobogrammaticInRange("50", "100")); }इनपुट
"50","100"
आउटपुट
3