Найдите непустое подмножество в массиве из N целых чисел такое, что сумма элементов подмножества делится на N

Опубликовано: 16 Января, 2022

Для массива из N целых чисел задача состоит в том, чтобы найти непустое подмножество такое, что сумма элементов подмножества делится на N. Выведите любое такое подмножество с его размером и индексами (индексирование на основе 1) элементов в исходный массив, если он существует.
Предпосылки: принцип голубятни
Примеры:

 Ввод: arr [] = {2, 3, 7, 1, 9}
Выход: 2
        1 2
Требуемое подмножество - это {2, 3}, индексы которого равны 1 и 2.


Ввод: arr [] = {2, 11, 4}
Выход: 2
        2 3
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход состоит в том, чтобы сгенерировать все возможные подмножества, используя набор мощности данного массива, вычислить их соответствующие суммы и проверить, делится ли сумма на 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
}
Output: 

2
1 2