সি++ কোড: বাইনারি স্ট্রিং থেকে ন্যূনতম সঠিক স্ট্রিং খুঁজুন

মান लीজিয়ে একটি বাইনারি স্ট্রিং S আছে যার দৈর্ঘ্য n এবং এর কোনো রিডান্ড্যান্ট লিডিং জিরো নেই। আমরা S-তে দুটি অপারেশন করতে পারি:

যে-কোনো দুটি আড়াঝড়া বিট সোয়াপ করা
সব "11" কে "1" দিয়ে রিপ্লেস করা

val(S) হলো S-এর ডেসিমেল রিপ্রেজেন্টেশন। আমাদের ন্যূনতম সঠিক স্ট্রিং খুঁজে বের করতে হবে, যেখানে সঠিক স্ট্রিং A, B-র চেয়ে ছোট হবে যদি val(A) < val(B) হয়।

উদাহরণ

ইনপুট: S = "1001"
আউটপুট: "100"
কারণ: "1001" → "1010" → "1100" → "100" (অপারেশনগুলো বিধি অনুযায়ী)۔

সমাধানের ধাপসমূহ

n := S-এর সাইজ
res := খালি স্ট্রিং
res := res + S[0]
for i := 1 to n-1:
    if S[i] == '0':
        res := res + "0"
return res

সি++ কোড উদাহরণ

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

string solve(string S) {
    int n = S.size();
    string res = "";
    res += S[0];
    for (int i = 1; i < n; i++) {
        if (S[i] == '0')
            res += "0";
    }
    return res;
}

int main() {
    string S = "1001";
    cout << solve(S) << endl;
}

ইনপুট

"1001"