यहां हम एक समस्या देखेंगे। मान लीजिए कि एक सरणी गिरफ्तारी दी गई है। हमें यह जांचना होगा कि क्या सरणी को दो भागों में विभाजित किया जा सकता है, जैसे -
- दोनों उप-सरणी के उप समान होंगे
- सभी तत्व, जो 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