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

给定一个由N个整数组成的数组，任务是找到一个非空子集，使子集的元素之和可被N整除。输出任何此类子集及其大小和原始数组中元素的索引（基于1的索引）。 先决条件： 鸽子洞原理 例如：

null

Input: arr[] = { 2, 3, 7, 1, 9 }Output: 2        1 2The required subset is { 2, 3 } whose indices are 1 and 2.Input: arr[] = {2, 11, 4}Output: 2        2 3

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

一种简单的方法是使用动力装置对于给定的数组，计算它们各自的和，并检查和是否可被N整除。 时间复杂性： O（2） ^N *N）、O（2） ^N )用于生成所有子集，O（N）用于计算每个子集的和。 有效方法： 考虑前缀和，我们得到：

前缀 ₀ =啊 ₀ 前缀 _1. =啊 ₀ +啊 _1. 前缀 _2. =啊 ₀ +啊 _1. +啊 _2. … 前缀 _N =啊 ₀ +啊 _1. +啊 _2. +…+啊 _N 不难看出 _L +啊 _L+1 +…+啊 _R （L）≤ R）等于前缀 _R – 前缀 _L-1 .如果任何连续子段之和可被N整除，则表示取前缀的模N后的剩余数 _R –前缀 _L-1 是零，也就是说。（前缀） _R –前缀 _L-1 )%N=0；分解模，前缀 _R %N–前缀 _L-1 %N=0 前缀 _R %N=前缀 _L-1 %N。

因为N（0，1，2…N-2，N-1）有（N）个前缀值和N个可能的余数。因此，根据鸽子洞原理，总是存在一个前缀末端相等的连续子段。如果在任何情况下，前缀 _L ，那么第一个L索引将给出子集。以下是上述方法的实施情况：

C++

                         // CPP Program to find Non empty                       
                         // subset such that its elements' sum                       
                         // is divisible by N                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to print the subset index and size                       
                         void                                     findNonEmptySubset(                                     int                                     arr[],                                     int                                     N)                       
                         {                       
           
                                                 // Hash Map to store the indices of residue upon                       
                                                 // taking modulo N of prefixSum                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > mp;                       
           
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < N; i++) {                       
                                                 // Calculating the residue of prefixSum                       
                                                 sum = (sum + arr[i]) % N;                       
           
                                                 // If the pre[i]%n==0                       
                                                 if                                     (sum == 0) {                       
                                                 // print size                       
                                                 cout << i + 1 << endl;                       
           
                                                 // Print the first i indices                       
                                                 for                                     (                                     int                                     j = 0; j <= i; j++)                       
                                                 cout << j + 1 <<                                     " "                                     ;                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // If this sum was seen earlier, then                       
                                                 // the contiguous subsegment has been found                       
                                                 if                                     (mp.find(sum) != mp.end()) {                       
                                                 // Print the size of subset                       
                                                 cout << (i - mp[sum]) << endl;                       
           
                                                 // Print the indices of contiguous subset                       
                                                 for                                     (                                     int                                     j = mp[sum] + 1; j <= i; j++)                       
                                                 cout << j + 1 <<                                     " "                                     ;                       
           
                                                 return                                     ;                       
                                                 }                       
                                                 else                       
                                                 mp[sum] = i;                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 2, 3, 7, 1, 9 };                       
                                                 int                                     N =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
           
                                                 findNonEmptySubset(arr, N);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java Program to find Non                       
                         // empty subset such that                       
                         // its elements' sum is                       
                         // divisible by N                       
                         import                                     java.io.*;                       
                         import                                     java.util.HashMap;                       
                         import                                     java.util.Map.Entry;                       
                         import                                     java.util.Map;                       
                         import                                     java.lang.*;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // Function to print the                       
                         // subset index and size                       
                         static                                     void                                     findNonEmptySubset(                                     int                                     arr[],                       
                                                 int                                     N)                       
                         {                       
           
                                                 // Hash Map to store the                       
                                                 // indices of residue upon                       
                                                 // taking modulo N of prefixSum                       
                                                 HashMap<Integer, Integer> mp =                       
                                                 new                                     HashMap<Integer, Integer>();                       
           
                                                 int                                     sum =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < N; i++)                       
                                                 {                       
                                                 // Calculating the                       
                                                 // residue of prefixSum                       
                                                 sum = (sum + arr[i]) % N;                       
           
                                                 // If the pre[i]%n==0                       
                                                 if                                     (sum ==                                     0                                     )                       
                                                 {                       
                                                 // print size                       
                                                 System.out.print(i +                                     1                                     +                                     ""                                     );                       
           
                                                 // Print the first i indices                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j <= i; j++)                       
                                                 System.out.print(j +                                     1                                     +                                     " "                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // If this sum was seen                       
                                                 // earlier, then the                       
                                                 // contiguous subsegment                       
                                                 // has been found                       
                                                 if                                     (mp.containsKey(sum) ==                                     true                                     )                       
                                                 {                       
                                                 // Print the size of subset                       
                                                 System.out.println((i -                       
                                                 mp.get(sum)));                       
           
                                                 // Print the indices of                       
                                                 // contiguous subset                       
                                                 for                                     (                                     int                                     j = mp.get(sum) +                                     1                                     ;                       
                                                 j <= i; j++)                       
                                                 System.out.print(j +                                     1                                     +                                     " "                                     );                       
           
                                                 return                                     ;                       
                                                 }                       
                                                 else                       
                                                 mp.put(sum,i);                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     arr[] = {                                     2                                     ,                                     3                                     ,                                     7                                     ,                                     1                                     ,                                     9                                     };                       
                                                 int                                     N = arr.length;                       
           
                                                 findNonEmptySubset(arr, N);                       
                         }                       
                         }                       

Python3

                         # Python3 Program to find Non                       
                         # empty subset such that its                       
                         # elements' sum is divisible                       
                         # by N                       
           
                         # Function to print the subset                       
                         # index and size                       
                         def                                     findNonEmptySubset(arr, N):                       
           
                                                 # Hash Map to store the indices                       
                                                 # of residue upon taking modulo                       
                                                 # N of prefixSum                       
                                                 mp                                     =                                     {}                       
           
                                                 Sum                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (N):                       
                                                 # Calculating the residue of                       
                                                 # prefixSum                       
                                                 Sum                                     =                                     (                                     Sum                                     +                                     arr[i])                                     %                                     N                       
           
                                                 # If the pre[i]%n==0                       
                                                 if                                     (                                     Sum                                     =                                     =                                     0                                     ) :                       
                                                 # print size                       
                                                 print                                     (i                                     +                                     1                                     )                       
           
                                                 # Print the first i indices                       
                                                 for                                     j                                     in                                     range                                     (i                                     +                                     1                                     ):                       
                                                 print                                     (j                                     +                                     1                                     , end                                     =                                     " "                                     )                       
                                                 return                       
           
                                                 # If this sum was seen earlier,                       
                                                 # then the contiguous subsegment                       
                                                 # has been found                       
                                                 if                                     Sum                                     in                                     mp :                       
                                   
                                                 # Print the size of subset                       
                                                 print                                     ((i                                     -                                     mp[                                     Sum                                     ]))                       
           
                                                 # Print the indices of contiguous                       
                                                 # subset                       
                                                 for                                     j                                     in                                     range                                     (mp[                                     Sum                                     ]                                     +                                     1                                     ,                       
                                                 i                                     +                                     1                                     ):                       
                                                 print                                     (j                                     +                                     1                                     , end                                     =                                     " "                                     )                       
           
                                                 return                       
                                                 else                                     :                       
                                                 mp[                                     Sum                                     ]                                     =                                     i                       
                                   
                         # Driver code                       
                         arr                                     =                                     [                                     2                                     ,                                     3                                     ,                                     7                                     ,                                     1                                     ,                                     9                                     ]                       
                         N                                     =                                     len                                     (arr)                       
                         findNonEmptySubset(arr, N)                       
           
                         # This code is contributed by divyeshrabadiya07                       

C#

                         // C# Program to find Non                       
                         // empty subset such that                       
                         // its elements' sum is                       
                         // divisible by N                       
           
                         using                                     System;                       
                         using                                     System.Collections ;                       
           
                         class                                     GFG                       
                         {                       
                                                 // Function to print the                       
                                                 // subset index and size                       
                                                 static                                     void                                     findNonEmptySubset(                                     int                                     []arr,                                     int                                     N)                       
                                                 {                       
                                   
                                                 // Hash Map to store the                       
                                                 // indices of residue upon                       
                                                 // taking modulo N of prefixSum                       
                                                 Hashtable mp =                                     new                                     Hashtable();                       
                                   
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < N; i++)                       
                                                 {                       
                                                 // Calculating the                       
                                                 // residue of prefixSum                       
                                                 sum = (sum + arr[i]) % N;                       
                                   
                                                 // If the pre[i]%n==0                       
                                                 if                                     (sum == 0)                       
                                                 {                       
                                                 // print size                       
                                                 Console.Write(i + 1 +                                     ""                                     );                       
                                   
                                                 // Print the first i indices                       
                                                 for                                     (                                     int                                     j = 0; j <= i; j++)                       
                                                 Console.Write(j + 1 +                                     " "                                     );                       
                                                 return                                     ;                       
                                                 }                       
                                   
                                                 // If this sum was seen                       
                                                 // earlier, then the                       
                                                 // contiguous subsegment                       
                                                 // has been found                       
                                                 if                                     (mp.ContainsKey(sum) ==                                     true                                     )                       
                                                 {                       
                                                 // Print the size of subset                       
                                                 Console.WriteLine(i - Convert.ToInt32(mp[sum]));                       
                                   
                                                 // Print the indices of                       
                                                 // contiguous subset                       
                                                 for                                     (                                     int                                     j = Convert.ToInt32(mp[sum]) + 1;                       
                                                 j <= i; j++)                       
                                                 Console.Write(j + 1 +                                     " "                                     );                       
                                   
                                                 return                                     ;                       
                                                 }                       
                                                 else                       
                                                 mp.Add(sum,i);                       
                                                 }                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []arr = { 2, 3, 7, 1, 9 };                       
                                                 int                                     N = arr.Length;                       
                                   
                                                 findNonEmptySubset(arr, N);                       
                                                 }                       
                                                 // This code is contributed by Ryuga                       
                         }                       

Javascript

                         <script>                       
                         // JavaScript Program to find Non empty                       
                         // subset such that its elements' sum                       
                         // is divisible by N                       
           
                         // Function to print the subset index and size                       
                         function                                     findNonEmptySubset( arr , N)                       
                         {                       
           
                                                 // Hash Map to store the indices of residue upon                       
                                                 // taking modulo N of prefixSum                       
                                                 var                                     mp =                                     new                                     Map();                       
           
                                                 var                                     sum = 0;                       
                                                 for                                     (let i = 0; i < N; i++)                       
                                                 {                       
                                   
                                                 // Calculating the residue of prefixSum                       
                                                 sum = (sum + arr[i]) % N;                       
           
                                                 // If the pre[i]%n==0                       
                                                 var                                     str=                                     ""                                     ;                       
                                                 if                                     (sum == 0)                       
                                                 {                       
                                   
                                                 // print size                       
                                                 console.log(i + 1 );                       
           
                                                 // Print the first i indices                       
                                                 for                                     (let j = 0; j <= i; j++)                       
                                                 str+=j + 1 +                                     " "                                     ;                       
                                                 console.log(str);                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // If this sum was seen earlier, then                       
                                                 // the contiguous subsegment has been found                       
                                                 if                                     (mp.has(sum))                       
                                                 {                       
                                   
                                                 // Print the size of subset                       
                                                 console.log(i - mp[sum]);                       
           
                                                 // Print the indices of contiguous subset                       
                                                 for                                     (let j = mp[sum] + 1; j <= i; j++)                       
                                                 str+=j + 1 +                                     " "                                     ;                       
                                                 console.log(str);                       
           
                                                 return                                     ;                       
                                                 }                       
                                                 else                       
                                                 mp[sum] = i;                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         var                                     arr =                                     new                                     Array( 2, 3, 7, 1, 9 );                       
                         var                                     N = arr.length;                       
           
                         findNonEmptySubset(arr, N);                       
           
                         // This code is contributed by ukasp.                       
           
                         </script>                       

输出：

21 2

时间复杂性： O（N），其中N是数组的大小。 辅助空间： O（N）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章