সমস্যা বিবরণ
n সংখ্যার একটি অ্যারে দেওয়া থাকলে, একটি নন-খালি সাবসেট খুঁজে বের করতে হবে যাতে সাবসেটটির উপাদানগুলোর যোগফল n দ্বারা বিভাজ্য হয়। এমন কোনো সাবসেট পাওয়া গেলে তার আকার এবং মূল অ্যারেতে উপাদানগুলির ইন্ডেক্স আউটপুট করা হবে।
উদাহরণ: ইনপুট [3, 2, 7, 1, 9] হলে আউটপুট হবে আকার 2 এবং ইন্ডেক্স [1, 2]।
সমাধানের ধাপসমূহ
- একটি ম্যাপ (my_map) সংজ্ঞায়িত করুন
- add := 0
- i = 0 থেকে N-1 পর্যন্ত লুপ চালান:
- add := (add + arr[i]) mod N
- যদি add == 0 হয়, তবে প্রথম i+1 উপাদানই উত্তর
- যদি add মানটি my_map-এ ইতিমধ্যে থাকে, তবে my_map[add]+1 থেকে i পর্যন্ত উপাদানগুলি উত্তর
- অন্যথায় 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
