Subconjunto con suma divisible por m

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *