इस समस्या में, हमें केवल 1 और -1 और एक पूर्णांक मान k से मिलकर एक सरणी arr[] दी जाती है। हमारा काम यह पता लगाना है कि क्या आकार K का कोई उपसमुच्चय -1 और +1 की सरणी में 0 योग के साथ है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट: arr[] ={-1, 1, -1, -1, 1 , 1, -1}, k =4
आउटपुट: हाँ
स्पष्टीकरण:
आकार 4, {-1, 1, -1, 1} का उपसमुच्चय। योग =-1 + 1 - 1 + 1 =0
समाधान दृष्टिकोण:
हमें यह जांचने की आवश्यकता है कि क्या k आकार का कोई उपसमुच्चय मौजूद है जिसका योग 0 के बराबर है। एक उपसमुच्चय के रूप में हम सरणी से किसी भी तत्व पर विचार कर सकते हैं, योग 0 होगा, यदि इसमें 1 और -1 की समान संख्या होगी। उपसमुच्चय। यह तभी संभव है जब उपसमुच्चय का आकार सम हो।
बस,
यदि k सम है, तो सत्य लौटें।
अगर k विषम है, तो झूठी वापसी करें।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <iostream>
using namespace std;
int countOne(int a[], int n) {
int i, count = 0;
for (i = 0; i < n; i++)
if (a[i] == 1)
count++;
return count;
}
bool isSubSetSumZeroFound(int arr[], int n, int K) {
int totalOne = countOne(arr, n);
int totalNegOne = n - totalOne;
return (K % 2 == 0 && totalOne >= K / 2 && totalNegOne >= K / 2);
}
int main() {
int arr[] = { 1, 1, -1, -1, 1, -1, 1, 1, -1 };
int size = sizeof(arr) / sizeof(arr[0]);
int K = 4;
if (isSubSetSumZeroFound(arr, size, K))
cout<<"Subset of size "<<K<<" with sum of all elements 0 exists.";
else
cout<<"No subset found";
return 0;
} आउटपुट
Subset of size 4 with sum of all elements 0 exists.