Dada una array arr[] que consta de N enteros y un entero K , la tarea es contar el número de subsecuencias de la array dada con promedio K .
Ejemplos:
Entrada: arr[] = {9, 7, 8, 9}, K = 8
Salida: 5
Explicación: Las subsecuencias que tienen un promedio de 8 son {8}, {9, 7}, {7, 9}, {9, 7 , 8}, {7, 8, 9}.Entrada: arr[] = {5, 5, 1}, K = 4
Salida: 0
Explicación: No se puede obtener tal subsecuencia
Enfoque ingenuo: el enfoque más simple para resolver el problema es usar la recursividad . Siga los pasos a continuación para resolver el problema:
- Son posibles dos opciones para cada elemento de la array, es decir, incluir el elemento actual en la suma o excluir el elemento actual de la suma y aumentar el índice actual para cada llamada recursiva.
- Para las dos posibilidades anteriores, devuelve el número de subsecuencias con promedio K .
- El caso base es comprobar si se ha alcanzado o no el último índice. El promedio en el caso base se puede calcular dividiendo la suma de los elementos de la array incluidos en esa subsecuencia.
- Si el promedio es igual a K , devuelve 1 . De lo contrario, devuelve 0 .
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica . Siga los pasos a continuación para resolver el problema:
- Inicialice una array 3D , digamos dp[][][] , donde dp[i][k][s] es la cantidad de formas de seleccionar k enteros de los primeros i enteros de modo que la suma de los enteros seleccionados sea s .
- Atraviesa la array .
- Hay dos posibles opciones disponibles para cada elemento, es decir, incluirlo o excluirlo.
- Si se incluye el elemento actual en el índice i , el siguiente estado del índice será i + 1 y el recuento de elementos seleccionados aumentará de k a k + 1 y la suma s aumentará a s + arr[i] .
- Si se excluye el elemento actual en el índice i , solo el índice i aumentará a i+1 y todos los demás estados permanecerán iguales.
- A continuación se muestra el estado de transición de dp para este problema:
Si se incluye i -ésimo elemento, entonces dp[i + 1][k + 1][s + arr[i]] += dp[i][k][s]
Si se excluye i -ésimo elemento, entonces dp[i + 1][k][s] += dp[i][k][s]
- Finalmente, la respuesta será la sumatoria de dp[N][j][K*j] para todo j ( 1 ≤ j ≤ N .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the dp states
int dp[101][101][1001];
// Function to find the count of
// subsequences having average K
int countAverage(int n, int K, int* arr)
{
// Base condition
dp[0][0][0] = 1;
// Three loops for three states
for (int i = 0; i < n; i++) {
for (int k = 0; k < n; k++) {
for (int s = 0; s <= 1000; s++) {
// Recurrence relation
dp[i + 1][k + 1][s + arr[i]]
+= dp[i][k][s];
dp[i + 1][k][s] += dp[i][k][s];
}
}
}
// Stores the sum of dp[n][j][K*j]
// all possible values of j with
// average K and sum K * j
int cnt = 0;
// Iterate over the range [1, N]
for (int j = 1; j <= n; j++) {
cnt += dp[n][j][K * j];
}
// Return the final count
return cnt;
}
// Driver Code
int main()
{
int arr[] = { 9, 7, 8, 9 };
int K = 8;
int N = sizeof(arr) / sizeof(arr[0]);
cout << countAverage(N, K, arr);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Stores the dp states
static int [][][]dp = new int[101][101][1001];
// Function to find the count of
// subsequences having average K
static int countAverage(int n, int K, int[] arr)
{
// Base condition
dp[0][0][0] = 1;
// Three loops for three states
for (int i = 0; i < n; i++)
{
for (int k = 0; k < n; k++)
{
for (int s = 0; s <= 100; s++)
{
// Recurrence relation
dp[i + 1][k + 1][s + arr[i]]
+= dp[i][k][s];
dp[i + 1][k][s] += dp[i][k][s];
}
}
}
// Stores the sum of dp[n][j][K*j]
// all possible values of j with
// average K and sum K * j
int cnt = 0;
// Iterate over the range [1, N]
for (int j = 1; j <= n; j++)
{
cnt += dp[n][j][K * j];
}
// Return the final count
return cnt;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 9, 7, 8, 9 };
int K = 8;
int N = arr.length;
System.out.print(countAverage(N, K, arr));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Stores the dp states dp = [[[0 for i in range(1001)] for i in range(101)] for i in range(101)] # Function to find the count of # subsequences having average K def countAverage(n, K, arr): global dp dp[0][0][0] = 1 # Three loops for three states for i in range(n): for k in range(n): for s in range(100): # Recurrence relation dp[i + 1][k + 1][s + arr[i]] += dp[i][k][s] dp[i + 1][k][s] += dp[i][k][s] # Stores the sum of dp[n][j][K*j] # all possible values of j with # average K and sum K * j cnt = 0 # Iterate over the range [1, N] for j in range(1, n + 1): cnt += dp[n][j][K * j] # Return the final count return cnt # Driver Code if __name__ == '__main__': arr= [9, 7, 8, 9] K = 8 N = len(arr) print(countAverage(N, K, arr)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
public class GFG
{
// Stores the dp states
static int [,,]dp = new int[101, 101, 1001];
// Function to find the count of
// subsequences having average K
static int countAverage(int n, int K, int[] arr)
{
// Base condition
dp[0, 0, 0] = 1;
// Three loops for three states
for (int i = 0; i < n; i++)
{
for (int k = 0; k < n; k++)
{
for (int s = 0; s <= 100; s++)
{
// Recurrence relation
dp[i + 1, k + 1, s + arr[i]]
+= dp[i, k, s];
dp[i + 1, k, s] += dp[i, k, s];
}
}
}
// Stores the sum of dp[n,j,K*j]
// all possible values of j with
// average K and sum K * j
int cnt = 0;
// Iterate over the range [1, N]
for (int j = 1; j <= n; j++)
{
cnt += dp[n, j, K * j];
}
// Return the readonly count
return cnt;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 9, 7, 8, 9 };
int K = 8;
int N = arr.Length;
Console.Write(countAverage(N, K, arr));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Stores the dp states
var dp = Array.from(Array(101), ()=> Array(101));
for(var i =0; i<101; i++)
for(var j =0; j<101; j++)
dp[i][j] = new Array(1001).fill(0);
// Function to find the count of
// subsequences having average K
function countAverage(n, K, arr)
{
// Base condition
dp[0][0][0] = 1;
// Three loops for three states
for (var i = 0; i < n; i++) {
for (var k = 0; k < n; k++) {
for (var s = 0; s <= 1000; s++) {
// Recurrence relation
dp[i + 1][k + 1][s + arr[i]]
+= dp[i][k][s];
dp[i + 1][k][s] += dp[i][k][s];
}
}
}
// Stores the sum of dp[n][j][K*j]
// all possible values of j with
// average K and sum K * j
var cnt = 0;
// Iterate over the range [1, N]
for (var j = 1; j <= n; j++) {
cnt += dp[n][j][K * j];
}
// Return the final count
return cnt;
}
// Driver Code
var arr = [9, 7, 8, 9];
var K = 8;
var N = arr.length
document.write( countAverage(N, K, arr));
</script>
Producción:
5
Complejidad de tiempo: O(S*N 2 ) donde S es la suma de la array.
Espacio Auxiliar: O(S*N 2 )
Publicación traducida automáticamente
Artículo escrito por PratikLath y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA