C++-এ অ্যারেকে সমান সম বিন্যাসে ভাগ করা দেওয়া শর্ত অনুযায়ী

এখানে আমরা একটি সমস্যা দেখব। ধরুন একটি অ্যারে arr দেওয়া আছে। আমাদের চেক করতে হবে অ্যারেটি কি দুটি অংশে ভাগ করা যায়, যাতে:

• দুটি সাব-অ্যারের সমান হবে
• ৫ দিয়ে বিভাজ্য সব উপাদান একই গ্রুপে থাকবে
• ৩ দিয়ে বিভাজ্য কিন্তু ৫ দিয়ে বিভাজ্য নয় এমন সব উপাদান একই গ্রুপে থাকবে
• অন্যান্য সব উপাদান অন্যান্য গ্রুপে থাকবে।

ধরুন অ্যারে উপাদানগুলো হল {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

C++ প্রোগ্রাম উদাহরণ

#include <iostream>
using namespace std;

bool isSplitArray(int* arr, int n, int start, int left_sum, int right_sum) {
    if (start == n) // যখন শেষে পৌঁছায়
        return left_sum == right_sum;
    if (arr[start] % 5 == 0) // যখন উপাদান ৫ দিয়ে বিভাজ্য, বাম সমে যোগ করুন
        left_sum += arr[start];
    else if (arr[start] % 3 == 0) // যখন উপাদান ৩ দিয়ে বিভাজ্য কিন্তু ৫ দিয়ে নয়, ডান সমে যোগ করুন
        right_sum += arr[start];
    else // অন্যথায় যেকোনো একটি সাব-অ্যারেতে যোগ করা যায়
        return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) || isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start]);
    // ৩ বা ৫ এর গুণিতক হলে এই লাইন এক্সিকিউট হবে
    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";
    }
    return 0;
}

আউটপুট

Can be split