এই সমস্যায়, আমাদের একটি অ্যারে দেওয়া আছে যাতে শুধু ১ এবং -১ রয়েছে এবং একটি পূর্ণসংখ্যা k। আমাদের কাজ হল K আকারের যেকোনো সাবসেটের যোগফল ০ কিনা তা খুঁজে বের করা।
উদাহরণ দিয়ে বুঝি,
ইনপুট: arr[] = {-1, 1, -1, -1, 1, 1, -1}, k = 4
আউটপুট: YES
ব্যাখ্যা:
আকার ৪-র একটি সাবসেট, {-1, 1, -1, 1}। যোগফল = -1 + 1 - 1 + 1 = 0
সমাধানের পদ্ধতি:
আমাদের যাচাই করতে হবে কি k আকারের যেকোনো সাবসেট আছে যার যোগফল ০। যেহেতু সাবসেটে যেকোনো এলিমেন্ট নেওয়া যায়, যোগফল ০ হবে যদি সাবসেটে ১ এবং -১-এর সংখ্যা সমান থাকে। এটি শুধু তখনই সম্ভব যখন সাবসেটের আকার জোড় হবে।
সহজ কথায়,
- যদি k জোড় হয়, true রিটার্ন করুন।
- যদি k বিজোড় হয়, false রিটার্ন করুন।
সমাধান দর্শানোর প্রোগ্রাম,
উদাহরণ
#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.
