এখানে আমরা একটি প্রোগ্রাম দেখতে পাব, যা একটি সংখ্যাকে সমান যোগফল সহ একাধিক ভাগে ভাগ করা যায় কিনা তা পরীক্ষা করতে পারে। ধরুন একটি সংখ্যা 74325 এর মতো, তাহলে এটিকে তিনটি ভাগে ভাগ করা যেতে পারে (7), (4, 3), (2, 5), সবগুলি একই উম মান।
এই সমস্যা সমাধানের জন্য আমাদের এই পদক্ষেপগুলি অনুসরণ করতে হবে৷
- সংখ্যাটিকে স্ট্রিং হিসাবে নিন
- অ্যারের উপসর্গ যোগ করার জন্য একটি অ্যারে ব্যবহার করুন
- এখন দ্বিতীয় এলিমেন্ট থেকে লাস্ট এলিমেন্টে যাওয়া, এবং প্রথম সেগমেন্ট হবে 0 থেকে i-1, যার যোগফল উপসর্গ_sum[i - 1] এ বসানো হবে।
- অন্য একটি ভেরিয়েবল ব্যবহার করুন যা 1 থেকে n পর্যন্ত অতিক্রম করে, তারপর যোগফল যোগ করতে থাকুন।
- যদি যেকোন পর্যায়ে যোগফলের মান উপসর্গ_সম[i – 1] এর সমান হয়, তাহলে সেগমেন্টটির যোগফল প্রথমটির সমান হয়।
- সেগমেন্টের যোগফলের মান 0 হিসাবে পুনরায় আরম্ভ করুন, তারপর পয়েন্টারটি সরাতে থাকুন।
- যদি কোনো পর্যায়ে সেগমেন্টের যোগফল উপসর্গ_সাম[i – 1] এর থেকে বেশি হয় তাহলে লুপ ভেঙে দিন
- যদি আমরা শেষ গন্তব্যে পৌঁছাই, এবং যদি শেষ সেগমেন্টের যোগফল প্রথম সেগমেন্টের যোগফলের সমান হয়, তাহলে একে সমান যোগফলের সেগমেন্টে ভাগ করা যেতে পারে।
উদাহরণ
#include <iostream>
using namespace std;
bool canBeSegmented(string str) {
int n = str.length();
int prefix_sum[n];
prefix_sum[0] = str[0] - '0';
for (int i = 1; i < n; i++) {
prefix_sum[i] = prefix_sum[i - 1] + (str[i] - '0');
}
for (int i = 1; i <= n - 1; i++) {
int sum = prefix_sum[i - 1];
int prev_sum = 0;
int it = i;
bool flag = false;
while (it < n) {
prev_sum += str[it] - '0';
if (prev_sum == sum) {
prev_sum = 0;
flag = true;
} else if (prev_sum > sum) {
break;
}
it++;
}
if (prev_sum == 0 && it == n && flag) {
return true;
}
}
return false;
}
int main() {
string s = "74325";
if (canBeSegmented(s))
cout << "Yes, This can be segmented into more than two segments";
else
cout << "No, This can not be segmented into more than two segments";
} আউটপুট
Yes, This can be segmented into more than two segments
