समस्या विवरण
मान लीजिए हमारे पास 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 प्रिंट करें
- j := 0 से i तक प्रिंट करें j+1
- वापस लौटें
- यदि add my_map में मौजूद है:
- (i - my_map[add]) प्रिंट करें
- j := my_map[add]+1 से i तक प्रिंट करें 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