এখানে আমরা একটি সমস্যা দেখতে পাব। ধরুন একটি অ্যারে arr দেওয়া আছে। আমাদের পরীক্ষা করতে হবে যে অ্যারেটিকে দুটি অংশে বিভক্ত করা যায়, যেমন −
- উভয় সাব-অ্যারের সাব একই হবে
- সমস্ত উপাদান, যা 5 এর একাধিক, একই গ্রুপে থাকবে
- সমস্ত উপাদান যা 3-এর একাধিক, কিন্তু 5-এর একাধিক নয়, একই গোষ্ঠীতে থাকবে
- অন্যান্য সব উপাদান অন্য গ্রুপে থাকবে।
ধরুন অ্যারের উপাদানগুলি হল {1, 4, 3}, তাহলে এটিকে বিভক্ত করা যেতে পারে, কারণ {1, 3}-এর যোগফল {4}-এর যোগফলের সমান, এবং প্রদত্ত অবস্থার জন্য গ্রুপগুলিও সঠিক।
অ্যালগরিদম
isSplitArray(arr, n, start, left_sum, right_sum) -
Begin if start = n, then return true when left_sum = right_sum, otherwise false if arr[start] is divisible by 5, then add arr[start] with the left_sum else if arr[start] is divisible by 3, then add arr[start] with the right_sum else return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) OR isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start]) isSplitArray(arr, n, start + 1, left_sum, right_sum) End
উদাহরণ
#include <iostream>
using namespace std;
bool isSplitArray(int* arr, int n, int start, int left_sum, int right_sum) {
if (start == n) //when it reaches at the end
return left_sum == right_sum;
if (arr[start] % 5 == 0) //when the element is divisible by 5, add to left sum
left_sum += arr[start];
else if (arr[start] % 3 == 0) //when the element is divisible by 3 but not 5, add to right sum
right_sum += arr[start];
else // otherwise it can be added to any of the sub-arrays
return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) || isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start]);
// For cases when element is multiple of 3 or 5.
return isSplitArray(arr, n, start + 1, left_sum, right_sum);
}
int main() {
int arr[] = {1, 4, 3};
int n = sizeof(arr)/sizeof(arr[0]);
if(isSplitArray(arr, n, 0, 0, 0)){
cout <<"Can be split";
} else {
cout <<"Can not be split";
}
} আউটপুট
Can be split
