C++ में एक के लिए बाइनरी प्रतिनिधित्व में एक संख्या को कम करने के चरणों की संख्या

मान लीजिए कि हमारे पास द्विआधारी रूप में एक संख्या है। हमें इन नियमों के तहत इसे घटाकर 1 करने के लिए चरणों की संख्या ज्ञात करनी होगी -

यदि वर्तमान संख्या सम है, तो हमें इसे 2 से भाग देना होगा।
यदि वर्तमान संख्या विषम है, तो आपको इसमें 1 जोड़ना होगा।

इसलिए, यदि इनपुट "1101" जैसा है, तो आउटपुट 6 होगा, क्योंकि "1101" 13 है। इसलिए, 13 विषम है, 1 जोड़ें और 14 प्राप्त करें। फिर 14 सम है, 2 से विभाजित करें और 7 प्राप्त करें। वह 7 विषम है, 1 जोड़ें और 8 प्राप्त करें।

फिर 8 फिर से है, वैसे ही, 2 से भाग दें और 4 प्राप्त करें। फिर 4 सम है, 2 से भाग दें और 2 प्राप्त करें, अंत में 2 सम है, 2 से भाग दें और 1 प्राप्त करें।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक फ़ंक्शन को परिभाषित करें addStrings(), यह एक सरणी num1, एक सरणी num2,
लेगा
एक सरणी रिट परिभाषित करें
कैरी:=0, योग:=0
num1 और num2 को उल्टा करें
मैं:=0, जे:=0
जबकि (i
- अगर i
  - योग :=कैरी + (num1[i] + num2[j])
  - रिट के अंत में योग मॉड 2 डालें
  - कैरी:=योग / 2
  - (i 1 से बढ़ाएँ)
  - (जम्मू को 1 से बढ़ाएं)
- अन्यथा जब i
  - योग :=कैरी + (num1[i])
  - रिट के अंत में योग मॉड 2 डालें
  - कैरी:=योग / 2
  - (i 1 से बढ़ाएँ)
- अन्यथा
  - योग :=कैरी + (num2[j])
  - रिट के अंत में योग मॉड 2 डालें
  - कैरी:=योग / 2
  - (जम्मू को 1 से बढ़ाएं)
यदि कैरी गैर-शून्य है, तो -
- रिट के अंत में कैरी डालें
मैं :=रिट का आकार
उत्तर:=रिक्त स्ट्रिंग
i>=0 के लिए, अपडेट करें (i से 1 घटाएं), करें -
- उत्तर:=उत्तर + (सेवानिवृत्त [i] + '0' का ASCII)
वापसी (यदि उत्तर का आकार 0 के समान है, तो "0", अन्यथा उत्तर)
फ़ंक्शन ऐडबाइनरी () को परिभाषित करें, यह एक सरणी ए, एक सरणी बी,
लेगा
वापसी addStrings(a, b)
एक सरणी makeVector को परिभाषित करें और v
. से कॉपी करें
- एक सरणी रिट परिभाषित करें
- इनिशियलाइज़ i:=0 के लिए, जब i
  - रिट के अंत में v[i] - ASCII का '0' डालें
- वापसी रिट
मुख्य विधि से निम्न कार्य करें,
रिट:=0
एक सरणी x =makeVector को s से परिभाषित करें
जबकि x> 1 का आकार, करें −
- (रिटर्न 1 से बढ़ाएं)
- यदि x का अंतिम अवयव 0 के समान है, तो -
  - x से अंतिम तत्व हटाएं
- अन्यथा
  - आकार 1 का एक सरणी अस्थायी परिभाषित करें
  - अस्थायी [0] :=1
  - एक्स:=मेक वेक्टर (ऐडबाइनरी (एक्स, अस्थायी))
वापसी रिट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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"