Dada una array arr[] de N enteros y un entero M , la tarea es encontrar el número de subsecuencias no vacías tales que la suma de la subsecuencia sea divisible por M.
Ejemplos:
Entrada: arr[] = {1, 2, 3}, M = 1
Salida: 7
El número de subconjuntos no vacíos de esta array es 7.
Dado que m = 1, m dividirá todos los subconjuntos posibles.
Entrada: arr[] = {1, 2, 3}, M = 2
Salida: 3
Enfoque: En este artículo se ha discutido un enfoque basado en programación dinámica con complejidad de tiempo O(N * SUM) donde N es la longitud de la array y SUM es la suma de todos los elementos de la array . En este artículo, se discutirá una mejora sobre el enfoque anterior. En lugar de la suma como uno de los estados de DP, (suma % m) se utilizará como uno de los estados de DP ya que es suficiente. Por lo tanto, la complejidad del tiempo se reduce a O(m * N). Relación de recurrencia:
dp[i][curr] = dp[i + 1][(curr + arr[i]) % m] + dp[i + 1][curr]
Definamos los estados ahora, dp[i][curr] simplemente significa el número de subconjuntos del subarreglo arr[i…N-1] tales que (suma de su elemento + curr) % m = 0 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define maxN 20
#define maxM 10
// To store the states of DP
int dp[maxN][maxM];
bool v[maxN][maxM];
// Function to find the required count
int findCnt(int* arr, int i, int curr, int n, int m)
{
// Base case
if (i == n) {
if (curr == 0)
return 1;
else
return 0;
}
// If the state has been solved before
// return the value of the state
if (v[i][curr])
return dp[i][curr];
// Setting the state as solved
v[i][curr] = 1;
// Recurrence relation
return dp[i][curr] = findCnt(arr, i + 1,
curr, n, m)
+ findCnt(arr, i + 1,
(curr + arr[i]) % m,
n, m);
}
// Driver code
int main()
{
int arr[] = { 3, 3, 3, 3 };
int n = sizeof(arr) / sizeof(int);
int m = 6;
cout << findCnt(arr, 0, 0, n, m) - 1;
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int maxN = 20;
static int maxM = 10;
// To store the states of DP
static int [][]dp = new int[maxN][maxM];
static boolean [][]v = new boolean[maxN][maxM];
// Function to find the required count
static int findCnt(int[] arr, int i,
int curr, int n, int m)
{
// Base case
if (i == n)
{
if (curr == 0)
return 1;
else
return 0;
}
// If the state has been solved before
// return the value of the state
if (v[i][curr])
return dp[i][curr];
// Setting the state as solved
v[i][curr] = true;
// Recurrence relation
return dp[i][curr] = findCnt(arr, i + 1,
curr, n, m) +
findCnt(arr, i + 1,
(curr + arr[i]) % m,
n, m);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 3, 3, 3 };
int n = arr.length;
int m = 6;
System.out.println(findCnt(arr, 0, 0, n, m) - 1);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach maxN = 20 maxM = 10 # To store the states of DP dp = [[0 for i in range(maxN)] for i in range(maxM)] v = [[0 for i in range(maxN)] for i in range(maxM)] # Function to find the required count def findCnt(arr, i, curr, n, m): # Base case if (i == n): if (curr == 0): return 1 else: return 0 # If the state has been solved before # return the value of the state if (v[i][curr]): return dp[i][curr] # Setting the state as solved v[i][curr] = 1 # Recurrence relation dp[i][curr] = findCnt(arr, i + 1, curr, n, m) + \ findCnt(arr, i + 1, (curr + arr[i]) % m, n, m) return dp[i][curr] # Driver code arr = [3, 3, 3, 3] n = len(arr) m = 6 print(findCnt(arr, 0, 0, n, m) - 1) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
static int maxN = 20;
static int maxM = 10;
// To store the states of DP
static int [,]dp = new int[maxN, maxM];
static bool [,]v = new bool[maxN, maxM];
// Function to find the required count
static int findCnt(int[] arr, int i,
int curr, int n, int m)
{
// Base case
if (i == n)
{
if (curr == 0)
return 1;
else
return 0;
}
// If the state has been solved before
// return the value of the state
if (v[i, curr])
return dp[i, curr];
// Setting the state as solved
v[i, curr] = true;
// Recurrence relation
return dp[i, curr] = findCnt(arr, i + 1,
curr, n, m) +
findCnt(arr, i + 1,
(curr + arr[i]) % m, n, m);
}
// Driver code
public static void Main()
{
int []arr = { 3, 3, 3, 3 };
int n = arr.Length;
int m = 6;
Console.WriteLine(findCnt(arr, 0, 0, n, m) - 1);
}
}
// This code is contributed by kanugargng
Javascript
<script>
// Javascript implementation of the approach
var maxN = 20
var maxM = 10
// To store the states of DP
var dp = Array.from(Array(maxN), () => Array(maxM));
var v = Array.from(Array(maxN), () => Array(maxM));
// Function to find the required count
function findCnt(arr, i, curr, n, m)
{
// Base case
if (i == n) {
if (curr == 0)
return 1;
else
return 0;
}
// If the state has been solved before
// return the value of the state
if (v[i][curr])
return dp[i][curr];
// Setting the state as solved
v[i][curr] = 1;
// Recurrence relation
dp[i][curr] = findCnt(arr, i + 1,
curr, n, m)
+ findCnt(arr, i + 1,
(curr + arr[i]) % m,
n, m);
return dp[i][curr];
}
// Driver code
var arr = [3, 3, 3, 3];
var n = arr.length;
var m = 6;
document.write( findCnt(arr, 0, 0, n, m) - 1);
</script>
7
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA