এখানে আমরা একটি প্রোগ্রাম দেখব যা চেক করবে একটি সংখ্যা একের অধিক সেগমেন্টে সমান যোগফলে ভাগ করা যায় কিনা। ধরুন একটি সংখ্যা ৭৪৩২৫, এটি তিনটি অংশে সেগমেন্ট করা যায়: (৭), (৪, ৩), (২, ৫) - সবার যোগফল সমান।
সমাধানের ধাপগুলো:
- সংখ্যাকে স্ট্রিং হিসেবে নিন
- প্রিফিক্স সাম অ্যারে ব্যবহার করুন
- দ্বিতীয় এলিমেন্ট থেকে শেষ পর্যন্ত ট্রাভার্স করুন, প্রথম সেগমেন্ট 0 থেকে i-1, যার যোগফল prefix_sum[i-1]-এ থাকবে
- একটি ভেরিয়েবল ব্যবহার করুন 1 থেকে n পর্যন্ত ট্রাভার্স করতে, যোগফল যোগ করুন
- যদি যোগফল prefix_sum[i-1] এর সমান হয়, তবে সেগমেন্টের যোগফল প্রথমটির সমান
- সেগমেন্ট সাম ০ করে দিন এবং পয়েন্টার বাড়ান
- যদি সেগমেন্ট সাম prefix_sum[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";
return 0;
}
আউটপুট
Yes, This can be segmented into more than two segments
