在N个整数的数组中找到一个非空的子集，以使子集的元素之和在C ++中可被N整除

Z时代
2024-01-10
分类：综合

假设我们有一个由n个数字组成的数组；我们必须找到一个非空子集，以使子集的元素之和可被n整除。因此，我们必须输出任何此类子集及其大小和原始数组中元素的索引（如果存在）。

因此，如果输入类似于[3，2，7，1，1，9]，则输出将为[2]，[1 2]。

为了解决这个问题，我们将遵循以下步骤-

定义一张映射my_map
加：= 0
对于初始化i：= 0，当i <N时，更新（将i增加1），执行-

my_map [add]：= i
打印（i-my_map [add]）
对于初始化j：= my_map [add] + 1，当j <= i时，更新（将j增加1），执行-
返回
打印j + 1

打印i + 1
对于初始化j：= 0，当j <= i时，更新（将j增加1），执行-
返回
打印j + 1

加：=（加+ arr [i]）mod N
如果add与0相同，则-
如果添加到my_map中，则-
除此以外

范例（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);
}