Dada una array de enteros, encuentre un número de subsecuencias tal que la suma de la subsecuencia sea divisible por m. Se da que la suma de los elementos de la array es pequeña.
Ejemplos:
Input : arr[] = {1, 2, 3};
m = 3;
Output : 3
Subsequence of given set are
{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3} and {1, 2, 3}.
And their sums are 1, 2, 3, 3, 5, 4 and 6.
Input : arr[] = {1, 2, 3, 4};
m = 2;
Output : 7
{2}, {4}, {1, 3}, {2, 4}, {1, 2, 3}, {1, 3, 4}
and {1, 2, 3, 4}
Una solución simple es generar todos los subconjuntos posibles. Para cada subconjunto, calcule su suma y, si la suma es múltiplo de m, incremente el resultado en 1. La complejidad temporal de este enfoque es O(2 len ) donde len es la longitud de la array de entrada.
Una solución eficiente (para valores pequeños) se basa en la solución de programación dinámica del problema de suma de subconjuntos . Hacemos una array 2D de tamaño sum x n.
C++
// C++ program which returns the Number of sub sequences
// (or subsets) which are divisible by m.
#include <bits/stdc++.h>
using namespace std;
// Use Dynamic Programming to find
// sum of subsequences.
int sumSubSequence(vector<int> arr, int len, int m)
{
// Find sum of array elements
int sum = 0;
for (auto x : arr)
sum += x;
// dp[i][j] would be > 0 if arr[0..i-1] has
// a subsequence with sum equal to j.
vector<vector<int> > dp(len + 1, vector<int>(sum + 1, 0));
// There is always sum equals zero
for (int i = 0; i <= len; i++)
dp[i][0]++;
// Fill up the dp table
for (int i = 1; i <= len; i++) {
dp[i][arr[i - 1]]++;
for (int j = 1; j <= sum; j++) {
if (dp[i - 1][j] > 0) {
dp[i][j]++;
dp[i][j + arr[i - 1]]++;
}
}
}
// Initialize the counter
int count = 0;
for (int j = 1; j <= sum; j++)
// Check if the sum exists
if (dp[len][j] > 0)
// check sum is divisible by m
if (j % m == 0)
count += dp[len][j];
return count;
}
// Driver Code
int main()
{
vector<int> arr{ 1, 2, 3 };
int m = 3;
int len = arr.size();
cout << sumSubSequence(arr, len, m) << endl;
return 0;
}
Java
// Java program which returns the Number of sub sequences
// (or subsets) which are divisible by m.
class GFG
{
// Use Dynamic Programming to find
// sum of subsequences.
static int sumSubSequence(int []arr, int len, int m)
{
// Find sum of array elements
int sum = 0;
for (int x : arr)
{
sum += x;
}
// dp[i][j] would be > 0 if arr[0..i-1] has
// a subsequence with sum equal to j.
int [][]dp = new int[len + 1][sum + 1];
// There is always sum equals zero
for (int i = 0; i <= len; i++)
dp[i][0]++;
// Fill up the dp table
for (int i = 1; i <= len; i++)
{
dp[i][arr[i - 1]]++;
for (int j = 1; j <= sum; j++)
{
if (dp[i - 1][j] > 0)
{
dp[i][j]++;
dp[i][j + arr[i - 1]]++;
}
}
}
// Initialize the counter
int count = 0;
for (int j = 1; j <= sum; j++)
// Check if the sum exists
if (dp[len][j] > 0)
// check sum is divisible by m
if (j % m == 0)
count += dp[len][j];
return count;
}
// Driver Code
public static void main(String[] args)
{
int []arr = { 1, 2, 3 };
int m = 3;
int len = arr.length;
System.out.print(sumSubSequence(arr, len, m) +"\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program which returns # the Number of sub sequences # (or subsets) which are divisible by m. # Use Dynamic Programming to find # sum of subsequences. def sumSubSequence(arr, length, m): # Find sum of array elements summ = 0 for i in arr: summ += i # dp[i][j] would be > 0 if arr[0..i-1] has # a subsequence with sum equal to j. dp = [[0 for i in range(summ + 1)] for j in range(length + 1)] # There is always sum equals zero for i in range(length + 1): dp[i][0] += 1 # Fill up the dp table for i in range(1, length + 1): dp[i][arr[i - 1]] += 1 for j in range(1, summ + 1): if dp[i - 1][j] > 0: dp[i][j] += 1 dp[i][j + arr[i - 1]] += 1 # Initialize the counter count = 0 for i in range(1, summ + 1): # Check if the sum exists if dp[length][i] > 0: # check sum is divisible by m if i % m == 0: count += dp[length][i] return count # Driver Code if __name__ == "__main__": arr = [1, 2, 3] m = 3 length = len(arr) print(sumSubSequence(arr, length, m)) # This code is contributed by # sanjeev2552
C#
// C# program which returns
// the Number of sub sequences
// (or subsets) which are
// divisible by m.
using System;
class GFG{
// Use Dynamic Programming
// to find sum of subsequences.
static int sumSubSequence(int []arr,
int len,
int m)
{
// Find sum of array elements
int sum = 0;
foreach (int x in arr)
{
sum += x;
}
// dp[i][j] would be > 0 if
// arr[0..i-1] has a
// subsequence with sum equal
// to j.
int [,]dp = new int[len + 1,
sum + 1];
// There is always sum equals
// zero
for (int i = 0; i <= len; i++)
dp[i, 0]++;
// Fill up the dp table
for (int i = 1; i <= len; i++)
{
dp[i, arr[i - 1]]++;
for (int j = 1; j <= sum; j++)
{
if (dp[i - 1, j] > 0)
{
dp[i, j]++;
dp[i, j + arr[i - 1]]++;
}
}
}
// Initialize the counter
int count = 0;
for (int j = 1; j <= sum; j++)
// Check if the sum exists
if (dp[len, j] > 0)
// check sum is divisible
// by m
if (j % m == 0)
count += dp[len, j];
return count;
}
// Driver Code
public static void Main(string[] args)
{
int []arr = {1, 2, 3};
int m = 3;
int len = arr.Length;
Console.Write(
sumSubSequence(arr,
len, m) + "\n");
}
}
// This code is contributed by Chitranayal
Javascript
<script>
// Javascript program which returns the Number of sub sequences
// (or subsets) which are divisible by m.
// Use Dynamic Programming to find
// sum of subsequences.
function sumSubSequence(arr,len,m)
{
// Find sum of array elements
let sum = 0;
for (let x=0;x<arr.length;x++)
{
sum += arr[x];
}
// dp[i][j] would be > 0 if arr[0..i-1] has
// a subsequence with sum equal to j.
let dp = new Array(len + 1);
for(let i=0;i<dp.length;i++)
{
dp[i]=new Array(sum+1);
for(let j=0;j<dp[i].length;j++)
{
dp[i][j]=0;
}
}
// There is always sum equals zero
for (let i = 0; i <= len; i++)
dp[i][0]++;
// Fill up the dp table
for (let i = 1; i <= len; i++)
{
dp[i][arr[i - 1]]++;
for (let j = 1; j <= sum; j++)
{
if (dp[i - 1][j] > 0)
{
dp[i][j]++;
dp[i][j + arr[i - 1]]++;
}
}
}
// Initialize the counter
let count = 0;
for (let j = 1; j <= sum; j++)
// Check if the sum exists
if (dp[len][j] > 0)
// check sum is divisible by m
if (j % m == 0)
count += dp[len][j];
return count;
}
// Driver Code
let arr=[ 1, 2, 3];
let m = 3;
let len = arr.length;
document.write(sumSubSequence(arr, len, m) +"<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
3
La complejidad temporal del enfoque anterior es O(len*sum) donde len es el tamaño de la array y sum es la suma de todos los enteros de la array.