Dada una array de N enteros, la tarea es encontrar un subconjunto no vacío tal que la suma de los elementos del subconjunto sea divisible por N. Genere cualquier subconjunto con su tamaño y los índices (indexación basada en 1) de los elementos en la array original si existe.
Requisitos previos: Ejemplos del principio del casillero
:
Input: arr[] = { 2, 3, 7, 1, 9 }
Output: 2
1 2
The required subset is { 2, 3 } whose indices are 1 and 2.
Input: arr[] = {2, 11, 4}
Output: 2
2 3
Un enfoque ingenuo será generar todos los subconjuntos posibles usando el Power Set de la array dada, calcular sus respectivas sumas y verificar si la suma es divisible por N.
Complejidad de tiempo: O(2 N * N), O(2 N ) para generar todos los subconjuntos y O(N) para calcular la suma de cada subconjunto.
Enfoque Eficiente: Al considerar Sumas de Prefijos, obtenemos:
prefixSum 0 = arr 0
prefixSum 1 = arr 0 + arr 1
prefixSum 2 = arr 0 + arr 1 + arr 2
…
prefixSum N = arr 0 + arr 1 + arr 2 + … + arr N
Se puede ver fácilmente que arr L + arr L+1 + … + arr R (L ≤ R) es igual a prefixSum R –
prefixSum L-1 . Si la suma de cualquier subsegmento contiguo es divisible por N, entonces
significa que el residuo al tomar el módulo N de prefixSum R – prefixSum L-1
es cero, es decir
(prefixSum R – prefixSum L-1 ) % N = 0;
Dividiendo el módulo,
prefixSum R % N – prefixSum L-1 % N = 0
prefixSum R % N = prefixSum L-1 % N.
Dado que hay (N) valores de prefixSums y N posibles residuos para N (0, 1, 2 … N-2, N-1). Por tanto, según el principio del casillero, siempre existe un subsegmento contiguo cuyos extremos del prefijo Suma son iguales. Si en algún caso, el prefijo L , entonces los primeros índices L darán el subconjunto.
A continuación se muestra la implementación del enfoque anterior:
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 + "\n");
// 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 + "\n");
// 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>
2 1 2
Complejidad de tiempo: O(N), donde N es el tamaño de la array.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA