ধরুন আমাদের n সংখ্যার একটি অ্যারে আছে; আমাদের একটি অ-খালি উপসেট খুঁজে বের করতে হবে যাতে উপসেটের উপাদানগুলির যোগফল n দ্বারা বিভাজ্য হয়। সুতরাং, যখন এটি উপস্থিত থাকে তখন আমাদেরকে এর আকার এবং মূল অ্যারের উপাদানগুলির সূচক সহ এই জাতীয় যে কোনও উপসেট আউটপুট করতে হবে৷
সুতরাং, যদি ইনপুটটি [3, 2, 7, 1, 9] এর মত হয়, তাহলে আউটপুট হবে [2], [1 2]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি মানচিত্র my_map সংজ্ঞায়িত করুন
- যোগ করুন :=0
- আরম্ভ করার জন্য i :=0, যখন i
- add :=(add + arr[i]) mod N
- যদি যোগ 0 এর মত হয়, তাহলে −
- প্রিন্ট i + 1
- j শুরু করার জন্য :=0, যখন j <=i, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), −
- করুন
- প্রিন্ট j + 1
- প্রত্যাবর্তন
- যদি my_map-এ যোগ করা হয়, তাহলে −
- মুদ্রণ (i - my_map[add])
- আরম্ভ করার জন্য j :=my_map[add] + 1, যখন j <=i, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), −
- করুন
- প্রিন্ট j + 1
- প্রত্যাবর্তন
- অন্যথায়
- my_map[add] :=i
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
void subset_find(int arr[], int N) {
unordered_map<int, int> my_map;
int add = 0;
for (int i = 0; i < N; i++) {
add = (add + arr[i]) % N;
if (add == 0) {
cout << i + 1 << endl;
for (int j = 0; j <= i; j++)
cout << j + 1 << " ";
return;
}
if (my_map.find(add) != my_map.end()) {
cout << (i - my_map[add]) << endl;
for (int j = my_map[add] + 1; j <= i; j++)
cout << j + 1 << " ";
return;
}
else
my_map[add] = i;
}
}
int main() {
int arr[] = {3, 2, 7, 1, 9};
int N = sizeof(arr) / sizeof(arr[0]);
subset_find(arr, N);
} ইনপুট
{3, 2, 7, 1, 9} আউটপুট
2 1 2
