मान लीजिए हमारे पास बाइनरी रूप में एक संख्या s है। हमें इसे 1 तक कम करने के चरणों की संख्या ज्ञात करनी है, निम्न नियमों के अनुसार:
- यदि वर्तमान संख्या सम है, तो इसे 2 से विभाजित करें।
- यदि वर्तमान संख्या विषम है, तो इसमें 1 जोड़ें।
उदाहरण के लिए, यदि इनपुट "1101" है, तो आउटपुट 6 होगा, क्योंकि "1101" दशमलव में 13 है। 13 विषम है, 1 जोड़ने पर 14 प्राप्त होता है। 14 सम है, 2 से विभाजित करने पर 7 प्राप्त होता है। 7 विषम है, 1 जोड़ने पर 8 प्राप्त होता है। 8 सम है, 2 से विभाजित करने पर 4, फिर 2, और अंत में 1 प्राप्त होता है।
हल करने की विधि
हम निम्न चरणों का पालन करेंगे:
addStrings()फ़ंक्शन परिभाषित करें, जो दो बाइनरी अंकों के सरणी लेता है और उनका योग लौटाता है।- दोनों सरणियों को उल्टा करें और बिटवाइज़ जोड़ करें, कैरी को संभालते हुए।
addBinary()फ़ंक्शनaddStrings()को कॉल करता है।makeVector()फ़ंक्शन स्ट्रिंग को पूर्णांक सरणी में बदलता है।- मुख्य विधि में, बाइनरी स्ट्रिंग को सरणी में बदलें और लूप चलाएं जब तक सरणी का आकार 1 से अधिक न हो जाए:
- चरण गणना बढ़ाएं।
- यदि अंतिम तत्व 0 है (सम), तो अंतिम तत्व हटाएं (2 से विभाजन)।
- अन्यथा (विषम), 1 जोड़ने के लिए
addBinary()का उपयोग करें और परिणाम को नई सरणी में बदलें। - कुल चरणों की संख्या लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class Solution { public: string addStrings(vector<int> num1, vector<int> num2){ vector<int> ret; int carry = 0; int sum = 0; reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); int i = 0; int j = 0; while (i < num1.size() || j < num2.size()) { if (i < num1.size() && j < num2.size()) { sum = carry + (num1[i]) + (num2[j]); ret.push_back(sum % 2); carry = sum / 2; i++; j++; } else if (i < num1.size()) { sum = carry + (num1[i]); ret.push_back(sum % 2); carry = sum / 2; i++; } else { sum = carry + (num2[j]); ret.push_back(sum % 2); carry = sum / 2; j++; } } if (carry) ret.push_back(carry); i = ret.size() - 1; string ans = ""; for (; i >= 0; i--) ans += (ret[i] + '0'); return ans.size() == 0 ? "0" : ans; } string addBinary(vector<int>& a, vector<int>& b){ return addStrings(a, b); } vector<int> makeVector(string v){ vector<int> ret; for (int i = 0; i < v.size(); i++) ret.push_back(v[i] - '0'); return ret; } int numSteps(string s){ int ret = 0; vector<int> x = makeVector(s); while (x.size() > 1) { ret++; if (x.back() == 0) { x.pop_back(); } else { vector<int> temp(1); temp[0] = 1; x = makeVector(addBinary(x, temp)); } } return ret; } }; main(){ Solution ob; cout << (ob.numSteps("1101")); }
इनपुट
"1101"
आउटपुट
6
