বাইনারি রিপ্রেজেন্টেশনে সংখ্যা এক করে আনার জন্য প্রয়োজনীয় ধাপের সংখ্যা C++-এ

সমস্যা বিবরণ

একটি বাইনারি স্ট্রিং s দেওয়া আছে। নিচের নিয়মাবলী অনুসরণ করে এটিকে ১ তে রূপান্তর করতে মোট কত ধাপ লাগবে তা বের করতে হবে:

• যদি বর্তমান সংখ্যা জোড় (even) হয়, তবে এটিকে ২ দিয়ে ভাগ করুন।
• যদি বর্তমান সংখ্যা বিজোড় (odd) হয়, তবে এটিতে ১ যোগ করুন।

উদাহরণ

ইনপুট: "1101" (বাইনারি) = ১৩ (ডেসিমাল)

1. ১৩ বিজোড় → ১ যোগ করুন = ১৪
2. ১৪ জোড় → ২ দিয়ে ভাগ করুন = ৭
3. ৭ বিজোড় → ১ যোগ করুন = ৮
4. ৮ জোড় → ২ দিয়ে ভাগ করুন = ৪
5. ৪ জোড় → ২ দিয়ে ভাগ করুন = ২
6. ২ জোড় → ২ দিয়ে ভাগ করুন = ১

মোট ধাপ = ৬

অ্যালগরিদম

বাইনারি স্ট্রিং বড় হলে সরাসরি ইন্টিজারে রূপান্তর করা যায় না। তাই স্ট্রিং রূপে ही বাইনারি যোগ এবং ভাগ অপারেশন করুন।

মূল ধাপসমূহ:

1. addStrings() ফাংশন: দুটি বাইনারি সংখ্যা (ভেক্টর আকারে) যোগ করে ফলাফল স্ট্রিং আকারে ফেরত দেয়।
2. makeVector() ফাংশন: বাইনারি স্ট্রিংকে ইন্টিজার ভেক্টরে রূপান্তর করে।
3. মূল লুপ:
   • যখন ভেক্টরের আকার ১-এর চেয়ে বড় থাকে, ধাপ সংখ্যা বাড়ান।
   • শেষ বিট ০ হলে (জোড়) → শেষ উপাদান মুছুন (২ দিয়ে ভাগ সমতুল্য)।
   • শেষ বিট ১ হলে (বিজোড়) → ১ যোগ করার জন্য addBinary কল করুন।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string addStrings(vector<int> num1, vector<int> num2) {
        vector<int> ret;
        int carry = 0, sum = 0;
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int i = 0, 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);
        string ans = "";
        for (int k = ret.size() - 1; k >= 0; k--)
            ans += (ret[k] + '0');
        return ans.empty() ? "0" : ans;
    }

    string addBinary(vector<int>& a, vector<int>& b) {
        return addStrings(a, b);
    }

    vector<int> makeVector(string v) {
        vector<int> ret;
        for (char c : v) ret.push_back(c - '0');
        return ret;
    }

    int numSteps(string s) {
        int steps = 0;
        vector<int> x = makeVector(s);
        while (x.size() > 1) {
            steps++;
            if (x.back() == 0) {
                x.pop_back(); // ২ দিয়ে ভাগ
            } else {
                vector<int> temp(1, 1); // ১ যোগ করার জন্য
                x = makeVector(addBinary(x, temp));
            }
        }
        return steps;
    }
};

int main() {
    Solution ob;
    cout << ob.numSteps("1101"); // আউটপুট: ৬
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n²) — যেখানে n হল বাইনারি স্ট্রিংয়ের দৈর্ঘ্য। প্রতিটি যোগ অপারেশন O(n) এবং যোগতত্ত্বিকভাবে O(n) বার যোগ হতে পারে।
• স্থান জটিলতা: O(n) — ভেক্টর এবং ইন্টারমিডিয়েট স্ট্রিং সংরক্ষণের জন্য।