ধরুন আমাদের n বিট সহ একটি বাইনারি স্ট্রিং S আছে। কোন অপ্রয়োজনীয় অগ্রণী শূন্য নেই। আমরা S−
এ দুটি ভিন্ন অপারেশন করতে পারি-
সংলগ্ন বিটগুলির যেকোনো জোড়া অদলবদল করুন
-
সমস্ত "11" কে "1"
দিয়ে প্রতিস্থাপন করুন
ধরুন val(S) হল S-এর দশমিক প্রতিনিধিত্ব। আমাদের ন্যূনতম সঠিক স্ট্রিং খুঁজে বের করতে হবে, যেখানে সঠিক স্ট্রিং A অন্য সঠিক স্ট্রিং 'B' থেকে কম যখন val(A)
সুতরাং, যদি ইনপুটটি S ="1001" এর মতো হয়, তাহলে আউটপুট হবে 100, কারণ আমরা "1001" -> "1010" -> "1100" -> "100" এর মতো অপারেশন করতে পারি।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
n := size of S res := a blank string res := res + S[0] for initialize i := 1, when i < n, update (increase i by 1), do: if S[i] is same as '0', then: res := res concatenate "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"
আউটপুট
100