বাইনারি রিপ্রেজেন্টেশনে একটি সংখ্যা কমিয়ে 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,
একটি অ্যারে ret সংজ্ঞায়িত করুন
বহন :=0, যোগফল :=0
বিপরীত num1 এবং num2
i :=0, j :=0
যখন (i করুন
- যদি i
  - যোগফল :=বহন + (সংখ্যা1[i] + সংখ্যা2[j])
  - ret এর শেষে যোগ mod 2 সন্নিবেশ করুন
  - বহন :=যোগফল / 2
  - (i 1 দ্বারা বাড়ান)
  - (j 1 দ্বারা বাড়ান)
- অন্যথায় যখন i
  - যোগফল :=বহন + (সংখ্যা1[i])
  - ret এর শেষে যোগ mod 2 সন্নিবেশ করুন
  - বহন :=যোগফল / 2
  - (i 1 দ্বারা বাড়ান)
- অন্যথায়
  - যোগফল :=বহন + (সংখ্যা2[জে])
  - ret এর শেষে যোগ mod 2 সন্নিবেশ করুন
  - বহন :=যোগফল / 2
  - (j 1 দ্বারা বাড়ান)
যদি বহন অ-শূন্য হয়, তাহলে -
- রিটের শেষে ক্যারি ঢোকান
i :=রিটের আকার
উত্তর :=ফাঁকা স্ট্রিং
i>=0 এর জন্য, আপডেট করুন (i 1 দ্বারা কম করুন), −
করুন
- ans :=ans + (ret[i] + ASCII of '0')
রিটার্ন (যদি উত্তরের আকার 0 এর মতো হয়, তাহলে "0", অন্যথায় উত্তর)
একটি ফাংশন সংজ্ঞায়িত করুন addBinary(), এটি একটি অ্যারে নেবে, একটি অ্যারে বি,
addStrings(a, b)
ফেরত দিন
একটি অ্যারে makeVector সংজ্ঞায়িত করুন এবং v
থেকে অনুলিপি করুন
- একটি অ্যারে ret সংজ্ঞায়িত করুন
- আরম্ভ করার জন্য i :=0, যখন i
  - সন্নিবেশ করান v[i] - ret-এর শেষে '0'-এর ASCII
- রিটার্ন রিটার্ন
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন,
ret :=0
s
থেকে একটি অ্যারে x =makeVector সংজ্ঞায়িত করুন
যখন x> 1 এর আকার, −
করুন
- (রেট 1 দ্বারা বৃদ্ধি করুন)
- যদি x এর শেষ উপাদানটি 0 এর মত হয়, তাহলে −
  - x
    থেকে শেষ উপাদান মুছুন
- অন্যথায়
  - আকার 1
    এর একটি অ্যারের তাপমাত্রা সংজ্ঞায়িত করুন
  - তাপমাত্রা[0] :=1
  - x :=makeVector(addBinary(x, temp))
রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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