সমস্যা বিবরণ
একটি বাইনারি স্ট্রিং str দেওয়া আছে। str দ্বারা উপস্থাপিত সংখ্যা তৈরির জন্য ন্যূনতম কতগুলো অপারেশন দরকার তা বের করতে হবে। শুধু নিচের অপারেশনগুলো করা যাবে:
- 2ˣ যোগ করা
- 2ˣ বিয়োগ করা
যদি বাইনারি স্ট্রিং "1000" হয়, তবে শুধু ১টি অপারেশন দরকার: 2³ যোগ করা।
যদি বাইনারি স্ট্রিং "101" হয়, তবে ২টি অপারেশন দরকার: 2² + 2⁰ যোগ করা।
উদাহরণ কোড
#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
