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

假设我们有一个由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);
    }

    输入值

    {3, 2, 7, 1, 9}

    输出结果

    2
    1 2
    猜你喜欢