Найдите непустое подмножество в массиве из N целых чисел такое, что сумма элементов подмножества делится на N
Для массива из N целых чисел задача состоит в том, чтобы найти непустое подмножество такое, что сумма элементов подмножества делится на N. Выведите любое такое подмножество с его размером и индексами (индексирование на основе 1) элементов в исходный массив, если он существует.
Предпосылки: принцип голубятни
Примеры:
Ввод: arr [] = {2, 3, 7, 1, 9} Выход: 2 1 2 Требуемое подмножество - это {2, 3}, индексы которого равны 1 и 2. Ввод: arr [] = {2, 11, 4} Выход: 2 2 3
Наивный подход состоит в том, чтобы сгенерировать все возможные подмножества, используя набор мощности данного массива, вычислить их соответствующие суммы и проверить, делится ли сумма на N.
Сложность времени: O (2 N * N), O (2 N ) для генерации всех подмножеств и O (N) для вычисления суммы каждого подмножества.
Эффективный подход: рассматривая суммы префиксов, мы получаем:
prefixSum0 = arr0
prefixSum1 = arr0 + arr1
prefixSum2 = arr0 + arr1 + arr2
…
prefixSumN = arr0 + arr1 + arr2 + … + arrN
It can be seen easily that arrL + arrL+1 + … + arrR (L ≤ R) equals to prefixSumR –
prefixSumL-1. If the sum of any contiguous subsegment is divisible by N, then it
means the residue upon taking modulo N of prefixSumR – prefixSumL-1
is zero, i.e.
(prefixSumR – prefixSumL-1) % N = 0;
Splitting the modulo,
prefixSumR % N – prefixSumL-1 % N = 0
prefixSumR % N = prefixSumL-1 % N.
Since there are (N) values of prefixSums and N possible residues for N (0, 1, 2 … N-2, N-1). Hence, according to the pigeonhole principle there always exists a contiguous subsegment whose prefixSum extremities are equal. If at any instance, prefixL, then the first L indexes will give the subset.
Below is the implementation of the above approach:
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 } |
2 1 2