Dado un conjunto de enteros distintos no negativos y un valor m, determine si hay un subconjunto del conjunto dado con suma divisible por m.
Restricciones de entrada
Tamaño del conjunto, es decir, n <= 1000000, m <= 1000
Ejemplos:
Input : arr[] = {3, 1, 7, 5};
m = 6;
Output : YES
Input : arr[] = {1, 6};
m = 5;
Output : NO
Este problema es una variante del problema de suma de subconjuntos . En el problema de suma de subconjuntos , verificamos si existe o no un subconjunto de suma dado, aquí debemos encontrar si existe algún subconjunto con suma divisible por m o no.
Enfoque ingenuo (usando recursividad):
C++
// C++ program to check if there is a subset
// with sum divisible by m.
#include <bits/stdc++.h>
using namespace std;
// Returns true if there is a subset
// of arr[] with sum divisible by m
bool helper(int N, int nums[], int sum, int idx, int m){
// if we reach last index
if(idx == N){
// and if the sum mod m is zero
if(sum && sum%m == 0){
// return
return true ;
}
return false ;
}
// 2 choices - to pick or to not pick
bool picked = helper(N, nums, sum+nums[idx], idx+1,m) ;
bool notPicked = helper(N, nums, sum, idx+1, m) ;
return picked || notPicked ;
}
bool modularSum(int arr[], int n, int m)
{
return helper(n, arr, 0, 0, m) ;
}
// Driver code
int main()
{
int arr[] = {1, 7};
int n = sizeof(arr)/sizeof(arr[0]);
int m = 5;
modularSum(arr, n, m) ? cout << "YES\n" :
cout << "NO\n";
return 0;
}
Java
// Java program to check if there is a subset
// with sum divisible by m.
class GFG {
// Returns true if there is a subset
// of arr[] with sum divisible by m
public static boolean helper(int N, int[] nums, int sum,
int idx, int m)
{
// if we reach last index
if (idx == N)
{
// and if the sum mod m is zero
if ((sum > 0) && (sum % m == 0)) {
// return
return true;
}
return false;
}
// 2 choices - to pick or to not pick
boolean picked
= helper(N, nums, sum + nums[idx], idx + 1, m);
boolean notPicked
= helper(N, nums, sum, idx + 1, m);
return picked || notPicked;
}
public static boolean modularSum(int[] arr, int n,
int m)
{
return helper(n, arr, 0, 0, m);
}
// driver code
public static void main(String[] args)
{
int arr[] = { 1, 7 };
int n = arr.length;
int m = 5;
if (modularSum(arr, n, m))
System.out.print("YES\n");
else
System.out.print("NO\n");
}
}
// this code is contribyted by phasing17
Python3
# Python3 program to check if there is a subset
# with sum divisible by m.
# Returns true if there is a subset
# of arr[] with sum divisible by m
def helper(N, nums, sum, idx, m):
# if we reach last index
if(idx == N):
# and if the sum mod m is zero
if(sum and sum%m == 0):
# return
return True
return False
# 2 choices - to pick or to not pick
picked = helper(N, nums, sum+nums[idx], idx+1,m)
notPicked = helper(N, nums, sum, idx+1, m)
return picked or notPicked
def modularSum(arr, n, m):
return helper(n, arr, 0, 0, m)
# Driver code
arr = [1, 7]
n = len(arr)
m = 5
print("YES") if modularSum(arr, n, m) else print("NO")
# This code is contributed by shinjanpatra.
C#
// C# program to check if there is a subset
// with sum divisible by m.
using System;
class GFG {
// Returns true if there is a subset
// of arr[] with sum divisible by m
public static bool helper(int N, int[] nums, int sum,
int idx, int m)
{
// if we reach last index
if (idx == N) {
// and if the sum mod m is zero
if ((sum > 0) && (sum % m == 0)) {
// return
return true;
}
return false;
}
// 2 choices - to pick or to not pick
bool picked
= helper(N, nums, sum + nums[idx], idx + 1, m);
bool notPicked = helper(N, nums, sum, idx + 1, m);
return picked || notPicked;
}
public static bool modularSum(int[] arr, int n, int m)
{
return helper(n, arr, 0, 0, m);
}
// driver code
public static void Main(string[] args)
{
int[] arr = { 1, 7 };
int n = arr.Length;
int m = 5;
if (modularSum(arr, n, m))
Console.Write("YES\n");
else
Console.Write("NO\n");
}
}
// this code is contribyted by phasing17
Javascript
<script>
// JavaScript program to check if there is a subset
// with sum divisible by m.
// Returns true if there is a subset
// of arr[] with sum divisible by m
function helper(N, nums, sum, idx, m)
{
// if we reach last index
if(idx == N)
{
// and if the sum mod m is zero
if(sum && sum%m == 0)
{
// return
return true ;
}
return false ;
}
// 2 choices - to pick or to not pick
let picked = helper(N, nums, sum+nums[idx], idx+1,m) ;
let notPicked = helper(N, nums, sum, idx+1, m) ;
return picked || notPicked ;
}
function modularSum(arr, n, m)
{
return helper(n, arr, 0, 0, m) ;
}
// Driver code
let arr = [1, 7];
let n = arr.length;
let m = 5;
modularSum(arr, n, m) ? document.write("YES","</br>") : document.write("NO","</br>");
// This code is contributed by shinjanpatra.
</script>
Producción
NO
Complejidad del tiempo: O(2 N )
Enfoque de memorización: como esto contiene subproblemas superpuestos, en lugar de llamar a la misma función una y otra vez, la almacenaremos en una array 2D.
Sigue el enfoque recursivo, pero en este método usamos una array 2D que se inicializa con -1 o cualquier valor negativo.
La array 2D se utiliza con fines de memorización para evitar llamadas recursivas repetidas desde el mismo estado.
A continuación se muestra la implementación del enfoque.
C++
// C++ program to check if there is a subset
// with sum divisible by m.
#include <bits/stdc++.h>
using namespace std;
// Returns true if there is a subset
// of arr[] with sum divisible by m
bool helper(int N, int nums[], int sum, int idx,
int m, vector<vector<int> >& dp)
{
// if we reach last index
if (idx == N) {
// and if the sum mod m is zero
if (sum && sum % m == 0) {
// return
return true;
}
return false;
}
if (dp[idx][sum] != -1) {
return dp[idx][sum];
}
// 2 choices - to pick or to not pick
bool picked
= helper(N, nums, sum + nums[idx],
idx + 1, m, dp);
bool notPicked = helper(N, nums, sum,
idx + 1, m, dp);
return dp[idx][sum] = picked || notPicked;
}
bool modularSum(int arr[], int n, int m)
{
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
vector<vector<int> > dp(n, vector<int>(sum + 1,
-1));
return helper(n, arr, 0, 0, m, dp);
}
// Driver code
int main()
{
int arr[] = { 1, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int m = 5;
modularSum(arr, n, m) ? cout << "YES\n"
: cout << "NO\n";
return 0;
}
// This code is contributed by Sanskar
Java
// Java program to check if there is a subset
// with sum divisible by m.
import java.util.Arrays;
class GFG {
// Returns true if there is a subset
// of arr[] with sum divisible by m
public static boolean helper(int N, int[] nums, int sum,
int idx, int m, int dp[][])
{
// if we reach last index
if (idx == N) {
// and if the sum mod m is zero
if ((sum > 0) && (sum % m == 0)) {
// return
return true;
}
return false;
}
if (dp[idx][sum] != -1) {
return dp[idx][sum] == 0 ? false : true;
}
// 2 choices - to pick or to not pick
boolean picked = helper(N, nums, sum + nums[idx],
idx + 1, m, dp);
boolean notPicked
= helper(N, nums, sum, idx + 1, m, dp);
dp[idx][sum] = notPicked || picked ? 1 : 0;
return notPicked || picked;
}
public static boolean modularSum(int[] arr, int n,
int m)
{
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
int dp[][] = new int[n][sum + 1];
for (int row[] : dp) {
Arrays.fill(row, -1);
}
return helper(n, arr, 0, 0, m, dp);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 7 };
int n = arr.length;
int m = 5;
if (modularSum(arr, n, m))
System.out.print("YES\n");
else
System.out.print("NO\n");
}
}
// This code is contributed by Sanskar
C#
// C# program to check if there is a subset
// with sum divisible by m.
using System;
using System.Collections.Generic;
class GFG {
// Returns true if there is a subset
// of arr[] with sum divisible by m
public static bool helper(int N, int[] nums, int sum,
int idx, int m, int[][] dp)
{
// if we reach last index
if (idx == N) {
// and if the sum mod m is zero
if ((sum > 0) && (sum % m == 0)) {
// return
return true;
}
return false;
}
if (dp[idx][sum] != -1) {
return dp[idx][sum] == 0 ? false : true;
}
// 2 choices - to pick or to not pick
bool picked = helper(N, nums, sum + nums[idx],
idx + 1, m, dp);
bool notPicked
= helper(N, nums, sum, idx + 1, m, dp);
dp[idx][sum] = notPicked || picked ? 1 : 0;
return notPicked || picked;
}
public static bool modularSum(int[] arr, int n, int m)
{
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
int[][] dp = new int[n][];
for (int i = 0; i < n; i++) {
dp[i] = new int[sum + 1];
Array.Fill(dp[i], -1);
}
return helper(n, arr, 0, 0, m, dp);
}
// Driver code
public static void Main(string[] args)
{
int[] arr = { 1, 7 };
int n = arr.Length;
int m = 5;
// Function call
if (modularSum(arr, n, m))
Console.Write("YES\n");
else
Console.Write("NO\n");
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript program to check if there is a subset
// with sum divisible by m.
// Returns true if there is a subset
// of arr[] with sum divisible by m
function helper(N, nums, sum, idx, m, dp)
{
// if we reach last index
if (idx == N) {
// and if the sum mod m is zero
if (sum && sum % m == 0) {
// return
return true;
}
return false;
}
if (dp[idx][sum] != -1) {
return dp[idx][sum];
}
// 2 choices - to pick or to not pick
let picked
= helper(N, nums, sum + nums[idx],
idx + 1, m, dp);
let notPicked = helper(N, nums, sum,
idx + 1, m, dp);
return dp[idx][sum] = picked || notPicked;
}
function modularSum(arr, n, m)
{
let sum = 0;
for (let i = 0; i < n; i++) {
sum += arr[i];
}
let dp = new Array(n).fill(0).map(()=>new Array(sum + 1).fill(-1));
return helper(n, arr, 0, 0, m, dp);
}
// Driver code
let arr = [ 1, 7 ];
let n = arr.length;
let m = 5;
modularSum(arr, n, m) ? document.write("YES","</br>")
: document.write("NO","</br>");
// This code is contributed by shinjanpatra
</script>
Producción
NO
Complejidad de tiempo: O(N*sum) donde sum es la suma de los elementos de la array.
Espacio Auxiliar: O(N*suma)
Enfoque eficiente:
Al ver la restricción de entrada, parece que la solución DP típica funcionará en tiempo O (nm). Pero en los límites de tiempo ajustados en la programación competitiva, la solución puede funcionar. También el espacio auxiliar es alto para la mesa DP, pero aquí hay una trampa.
Si n > m siempre habrá un subconjunto con suma divisible por m (lo cual es fácil de probar con el principio del casillero ). Entonces necesitamos manejar solo casos de n <= m .
Para n <= m , creamos una tabla DP booleana que almacenará el estado de cada valor de 0 a m-1, que son posibles sumas de subconjuntos (módulo m) que se han encontrado hasta ahora.
Ahora recorremos cada elemento de la array dada arr[], y agregamos (módulo m) j que tienen DP[j] = verdadero, y almacenamos todos los (j+arr[i])%m posibles sumas de subconjuntos en una array booleana temp, y al final de la iteración sobre j, actualizamos la tabla DP con temp. También agregamos arr[i] a DP, es decir, DP[arr[i]%m] = true.
Al final, si DP[0] es verdadero, entonces significa SÍ, existe un subconjunto con una suma que es divisible por m, de lo contrario, NO.
C++
// C++ program to check if there is a subset
// with sum divisible by m.
#include <bits/stdc++.h>
using namespace std;
// Returns true if there is a subset
// of arr[] with sum divisible by m
bool modularSum(int arr[], int n, int m)
{
if (n > m)
return true;
// This array will keep track of all
// the possible sum (after modulo m)
// which can be made using subsets of arr[]
// initialising boolean array with all false
bool DP[m];
memset(DP, false, m);
// we'll loop through all the elements of arr[]
for (int i=0; i<n; i++)
{
// anytime we encounter a sum divisible
// by m, we are done
if (DP[0])
return true;
// To store all the new encountered sum (after
// modulo). It is used to make sure that arr[i]
// is added only to those entries for which DP[j]
// was true before current iteration.
bool temp[m];
memset(temp,false,m);
// For each element of arr[], we loop through
// all elements of DP table from 1 to m and
// we add current element i. e., arr[i] to
// all those elements which are true in DP
// table
for (int j=0; j<m; j++)
{
// if an element is true in DP table
if (DP[j] == true)
{
if (DP[(j+arr[i]) % m] == false)
// We update it in temp and update
// to DP once loop of j is over
temp[(j+arr[i]) % m] = true;
}
}
// Updating all the elements of temp
// to DP table since iteration over
// j is over
for (int j=0; j<m; j++)
if (temp[j])
DP[j] = true;
// Also since arr[i] is a single element
// subset, arr[i]%m is one of the possible
// sum
DP[arr[i]%m] = true;
}
return DP[0];
}
// Driver code
int main()
{
int arr[] = {1, 7};
int n = sizeof(arr)/sizeof(arr[0]);
int m = 5;
modularSum(arr, n, m) ? cout << "YES\n" :
cout << "NO\n";
return 0;
}
Java
// Java program to check if there is a subset
// with sum divisible by m.
import java.util.Arrays;
class GFG {
// Returns true if there is a subset
// of arr[] with sum divisible by m
static boolean modularSum(int arr[],
int n, int m)
{
if (n > m)
return true;
// This array will keep track of all
// the possible sum (after modulo m)
// which can be made using subsets of arr[]
// initialising boolean array with all false
boolean DP[]=new boolean[m];
Arrays.fill(DP, false);
// we'll loop through all the elements
// of arr[]
for (int i = 0; i < n; i++)
{
// anytime we encounter a sum divisible
// by m, we are done
if (DP[0])
return true;
// To store all the new encountered sum
// (after modulo). It is used to make
// sure that arr[i] is added only to
// those entries for which DP[j]
// was true before current iteration.
boolean temp[] = new boolean[m];
Arrays.fill(temp, false);
// For each element of arr[], we loop
// through all elements of DP table
// from 1 to m and we add current
// element i. e., arr[i] to all those
// elements which are true in DP table
for (int j = 0; j < m; j++)
{
// if an element is true in
// DP table
if (DP[j] == true)
{
if (DP[(j + arr[i]) % m] == false)
// We update it in temp and update
// to DP once loop of j is over
temp[(j + arr[i]) % m] = true;
}
}
// Updating all the elements of temp
// to DP table since iteration over
// j is over
for (int j = 0; j < m; j++)
if (temp[j])
DP[j] = true;
// Also since arr[i] is a single
// element subset, arr[i]%m is one
// of the possible sum
DP[arr[i] % m] = true;
}
return DP[0];
}
//driver code
public static void main(String arg[])
{
int arr[] = {1, 7};
int n = arr.length;
int m = 5;
if(modularSum(arr, n, m))
System.out.print("YES\n");
else
System.out.print("NO\n");
}
}
//This code is contributed by Anant Agarwal.
Python3
# Python3 program to check if there is
# a subset with sum divisible by m.
# Returns true if there is a subset
# of arr[] with sum divisible by m
def modularSum(arr, n, m):
if (n > m):
return True
# This array will keep track of all
# the possible sum (after modulo m)
# which can be made using subsets of arr[]
# initialising boolean array with all false
DP = [False for i in range(m)]
# we'll loop through all the elements of arr[]
for i in range(n):
# anytime we encounter a sum divisible
# by m, we are done
if (DP[0]):
return True
# To store all the new encountered sum (after
# modulo). It is used to make sure that arr[i]
# is added only to those entries for which DP[j]
# was true before current iteration.
temp = [False for i in range(m)]
# For each element of arr[], we loop through
# all elements of DP table from 1 to m and
# we add current element i. e., arr[i] to
# all those elements which are true in DP
# table
for j in range(m):
# if an element is true in DP table
if (DP[j] == True):
if (DP[(j + arr[i]) % m] == False):
# We update it in temp and update
# to DP once loop of j is over
temp[(j + arr[i]) % m] = True
# Updating all the elements of temp
# to DP table since iteration over
# j is over
for j in range(m):
if (temp[j]):
DP[j] = True
# Also since arr[i] is a single element
# subset, arr[i]%m is one of the possible
# sum
DP[arr[i] % m] = True
return DP[0]
# Driver code
arr = [1, 7]
n = len(arr)
m = 5
print("YES") if(modularSum(arr, n, m)) else print("NO")
# This code is contributed by Anant Agarwal.
C#
// C# program to check if there is
// a subset with sum divisible by m.
using System;
class GFG {
// Returns true if there is a subset
// of arr[] with sum divisible by m
static bool modularSum(int []arr, int n,
int m)
{
if (n > m)
return true;
// This array will keep track of all
// the possible sum (after modulo m)
// which can be made using subsets of arr[]
// initialising boolean array with all false
bool []DP=new bool[m];
for (int l=0;l<DP.Length;l++)
DP[l]=false;
// we'll loop through all the elements of arr[]
for (int i=0; i<n; i++)
{
// anytime we encounter a sum divisible
// by m, we are done
if (DP[0])
return true;
// To store all the new encountered sum (after
// modulo). It is used to make sure that arr[i]
// is added only to those entries for which DP[j]
// was true before current iteration.
bool []temp=new bool[m];
for (int l=0;l<temp.Length;l++)
temp[l]=false;
// For each element of arr[], we loop through
// all elements of DP table from 1 to m and
// we add current element i. e., arr[i] to
// all those elements which are true in DP
// table
for (int j=0; j<m; j++)
{
// if an element is true in DP table
if (DP[j] == true)
{
if (DP[(j+arr[i]) % m] == false)
// We update it in temp and update
// to DP once loop of j is over
temp[(j+arr[i]) % m] = true;
}
}
// Updating all the elements of temp
// to DP table since iteration over
// j is over
for (int j=0; j<m; j++)
if (temp[j])
DP[j] = true;
// Also since arr[i] is a single element
// subset, arr[i]%m is one of the possible
// sum
DP[arr[i]%m] = true;
}
return DP[0];
}
//driver code
public static void Main()
{
int []arr = {1, 7};
int n = arr.Length;
int m = 5;
if(modularSum(arr, n, m))
Console.Write("YES\n");
else
Console.Write("NO\n");
}
}
//This code is contributed by Anant Agarwal.
PHP
<?php
// Php program to check if there is a
// subset with sum divisible by m.
// Returns true if there is a subset
// of arr[] with sum divisible by m
function modularSum($arr, $n, $m)
{
if ($n > $m)
return true;
// This array will keep track of all
// the possible sum (after modulo m)
// which can be made using subsets of arr[]
// initialising boolean array with all false
$DP = Array_fill(0, $m, false);
// we'll loop through all the elements of arr[]
for ($i = 0; $i < $n; $i++)
{
// anytime we encounter a sum divisible
// by m, we are done
if ($DP[0])
return true;
// To store all the new encountered sum
// (after modulo). It is used to make
// sure that arr[i] is added only to those
// entries for which DP[j] was true before
// current iteration.
$temp = array_fill(0, $m, false) ;
// For each element of arr[], we loop through
// all elements of DP table from 1 to m and
// we add current element i. e., arr[i] to
// all those elements which are true in DP
// table
for ($j = 0; $j < $m; $j++)
{
// if an element is true in DP table
if ($DP[$j] == true)
{
if ($DP[($j + $arr[$i]) % $m] == false)
// We update it in temp and update
// to DP once loop of j is over
$temp[($j + $arr[$i]) % $m] = true;
}
}
// Updating all the elements of temp
// to DP table since iteration over
// j is over
for ($j = 0; $j < $m; $j++)
if ($temp[$j])
$DP[$j] = true;
// Also since arr[i] is a single element
// subset, arr[i]%m is one of the possible
// sum
$DP[$arr[$i] % $m] = true;
}
return $DP[0];
}
// Driver Code
$arr = array(1, 7);
$n = sizeof($arr);
$m = 5;
if (modularSum($arr, $n, $m) == true )
echo "YES\n";
else
echo "NO\n";
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript program to check if there is
// a subset with sum divisible by m.
// Returns true if there is a subset
// of arr[] with sum divisible by m
function modularSum(arr, n, m)
{
if (n > m)
return true;
// This array will keep track of all
// the possible sum (after modulo m)
// which can be made using subsets of arr[]
// initialising boolean array with all false
let DP = new Array(m);
for (let l=0;l<m;l++)
DP[l]=false;
// we'll loop through all the elements of arr[]
for (let i=0; i<n; i++)
{
// anytime we encounter a sum divisible
// by m, we are done
if (DP[0])
return true;
// To store all the new encountered sum (after
// modulo). It is used to make sure that arr[i]
// is added only to those entries for which DP[j]
// was true before current iteration.
let temp=new Array(m);
for (let l=0;l<m;l++)
temp[l]=false;
// For each element of arr[], we loop through
// all elements of DP table from 1 to m and
// we add current element i. e., arr[i] to
// all those elements which are true in DP
// table
for (let j=0; j<m; j++)
{
// if an element is true in DP table
if (DP[j] == true)
{
if (DP[(j+arr[i]) % m] == false)
// We update it in temp and update
// to DP once loop of j is over
temp[(j+arr[i]) % m] = true;
}
}
// Updating all the elements of temp
// to DP table since iteration over
// j is over
for (let j=0; j<m; j++)
if (temp[j])
DP[j] = true;
// Also since arr[i] is a single element
// subset, arr[i]%m is one of the possible
// sum
DP[arr[i]%m] = true;
}
return DP[0];
}
let arr = [1, 7];
let n = arr.length;
let m = 5;
if(modularSum(arr, n, m))
document.write("YES" + "</br>");
else
document.write("NO" + "</br>");
</script>
Producción
NO
Complejidad de tiempo: O(m^2)
Espacio auxiliar: O(m)
Este artículo es una contribución de Pratik Chhajer . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA