সমস্যা বিবৃতি
একটি বাইনারি স্ট্রিং str দেওয়া. str দ্বারা উপস্থাপিত সংখ্যা তৈরি করতে সঞ্চালিত করা প্রয়োজন ন্যূনতম সংখ্যক অপারেশন খুঁজুন। শুধুমাত্র নিম্নলিখিত ক্রিয়াকলাপগুলি সম্পাদন করা যেতে পারে -
- 2 x যোগ করুন
- ২ বিয়োগ করুন x
যদি বাইনারি স্ট্রিং হয় "1000" তাহলে আমাদের শুধুমাত্র 1টি অপারেশন করতে হবে অর্থাৎ 2 3 যোগ করুন
যদি বাইনারি স্ট্রিং "101" হয় তবে আমাদের 2টি অপারেশন করতে হবে যেমন 2 2 যোগ করুন + 2 0
উদাহরণ
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int getMinOperations(string s){
reverse(s.begin(), s.end());
int n = s.length();
int result[n + 1][2];
if (s[0] == '0') {
result[0][0] = 0;
} else {
result[0][0] = 1;
}
result[0][1] = 1;
for (int i = 1; i < n; ++i) {
if (s[i] == '0') {
result[i][0] = result[i - 1][0];
result[i][1] = 1 + min(result[i - 1][1],
result[i - 1][0]);
} else {
result[i][1] = result[i - 1][1];
result[i][0] = 1 + min(result[i - 1][0],
result[i - 1][1]);
}
}
return result[n - 1][0];
}
int main(){
string str = "101";
cout << "Minimum required operations = " << getMinOperations(str) << endl;
return 0;
} আউটপুট
আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
তৈরি করেMinimum required operations = 2
