N पूर्णांकों की एक सरणी में एक गैर-खाली उपसमुच्चय खोजें जैसे कि उपसमुच्चय के तत्वों का योग N से C++ में विभाज्य हो

मान लीजिए हमारे पास n संख्याओं की एक सरणी है; हमें एक गैर-रिक्त उपसमुच्चय को खोजना है जैसे कि उपसमुच्चय के तत्वों का योग n से विभाज्य हो। इसलिए, हमें ऐसे किसी भी उपसमुच्चय को उसके आकार और मूल सरणी में तत्वों के सूचकांक के साथ आउटपुट करना होगा जब वह मौजूद हो।

इसलिए, अगर इनपुट [3, 2, 7, 1, 9] जैसा है, तो आउटपुट [2], [1 2] होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक मानचित्र my_map परिभाषित करें
• जोड़ें:=0
• इनिशियलाइज़ i :=0 के लिए, जब i करें
• जोड़ें :=(+ arr[i] जोड़ें) mod N
• यदि जोड़ 0 के समान है, तो −
  • i + 1 प्रिंट करें
  • इनिशियलाइज़ j :=0 के लिए, जब j <=i, अपडेट करें (j को 1 से बढ़ाएँ), −
    करें
    • प्रिंट जे + 1
  • वापसी
• यदि my_map में जोड़ें, तो −
  • प्रिंट करें (i - my_map[add])
  • इनिशियलाइज़ j :=my_map[add] + 1 के लिए, जब j <=i, अपडेट (j को 1 से बढ़ाएँ), −
    करें
    • प्रिंट जे + 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