Dada una array arr[] que consta de N enteros, la tarea es encontrar el número de formas de dividir la array en subarreglos no vacíos de modo que la suma del i -ésimo subarreglo sea divisible por i .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}
Salida: 3
Explicación: Las
siguientes son las formas de dividir el arreglo en un subarreglo no vacío como:
- Dividir el arreglo en subarreglo como {1}, {2}, {3}, {4} y la suma de cada uno del i-ésimo subarreglo es divisible por i.
- Dividir la array en subarreglo como {1, 2, 3}, {4} y cada uno de los i-ésimo subarreglo es divisible por i.
- Divida la array en subarreglo como {1, 2, 3, 4} y cada uno del i-ésimo subarreglo es divisible por i.
Como solo hay 3 formas posibles de dividir la array dada. Por lo tanto, imprime 3.
Entrada: arr[ ] = {1, 1, 1, 1, 1}
Salida: 3
Enfoque: el problema dado se puede resolver utilizando la programación dinámica porque tiene subproblemas superpuestos y una subestructura óptima. Los subproblemas se pueden almacenar en la tabla dp[][] usando memoization donde dp[i][j] almacena el número de particiones hasta el i-ésimo índice de arr[] en j subarreglo no vacío. Esta idea se puede implementar usando la array Prefix Sum pre[] que almacena la suma de todos los elementos hasta cada i -ésimo índice y dp[i][j] se puede calcular como la suma de dp[k][j – 1] para todos los valores de k < i tales que (pre[i] – pre[k]) es un múltiplo de j . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una variable, digamos contar , que almacena el número de posibles divisiones de la array dada en subarreglos.
- Encuentre la suma del prefijo de la array y guárdela en otra array, digamos prefix[] .
- Inicialice una array 2D , digamos dp[][] que almacena todos los estados superpuestos dp[i][j] .
- Iterar sobre el rango [0, N] usando la variable i e iterar anidado sobre el rango [N, 0] usando la variable j y realizar los siguientes pasos:
- Incremente el valor de dp[j + 1][pre[i + 1] % (j + 1)] por el valor de dp[j][pre[i + 1] % j] ya que esto indica el recuento de particiones hasta índice i en j subsecuencia continua divisible por (j + 1) .
- Si el valor de i es (N – 1) , entonces actualice el valor de count por dp[j][pre[i + 1] % j] .
- Después de completar los pasos anteriores, imprima el valor de conteo como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count ways to split
// an array into subarrays such that
// sum of the i-th subarray is
// divisible by i
int countOfWays(int arr[], int N)
{
// Stores the prefix sum of array
int pre[N + 1] = { 0 };
for (int i = 0; i < N; i++) {
// Find the prefix sum
pre[i + 1] = pre[i] + arr[i];
}
// Initialize dp[][] array
int dp[N + 1][N + 1];
memset(dp, 0, sizeof(dp));
dp[1][0]++;
// Stores the count of splitting
int ans = 0;
// Iterate over the range [0, N]
for (int i = 0; i < N; i++) {
for (int j = N; j >= 1; j--) {
// Update the dp table
dp[j + 1][pre[i + 1] % (j + 1)]
+= dp[j][pre[i + 1] % j];
// If the last index is
// reached, then add it
// to the variable ans
if (i == N - 1) {
ans += dp[j][pre[i + 1] % j];
}
}
}
// Return the possible count of
// splitting of array into subarrays
return ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << countOfWays(arr, N);
return 0;
}
Java
// Java program for the above approach
public class GFG {
// Function to count ways to split
// an array into subarrays such that
// sum of the i-th subarray is
// divisible by i
static int countOfWays(int arr[], int N)
{
// Stores the prefix sum of array
int pre[] = new int[N + 1];
for (int i = 0; i < N; i++) {
// Find the prefix sum
pre[i + 1] = pre[i] + arr[i];
}
// Initialize dp[][] array
int dp[][] = new int [N + 2][N + 2];
dp[1][0]++;
// Stores the count of splitting
int ans = 0;
// Iterate over the range [0, N]
for (int i = 0; i < N; i++) {
for (int j = N; j >= 1; j--) {
// Update the dp table
dp[j + 1][pre[i + 1] % (j + 1)]
+= dp[j][pre[i + 1] % j];
// If the last index is
// reached, then add it
// to the variable ans
if (i == N - 1) {
ans += dp[j][pre[i + 1] % j];
}
}
}
// Return the possible count of
// splitting of array into subarrays
return ans;
}
// Driver Code
public static void main (String[] args) {
int arr[] = { 1, 2, 3, 4 };
int N = arr.length;
System.out.println(countOfWays(arr, N));
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach import numpy as np # Function to count ways to split # an array into subarrays such that # sum of the i-th subarray is # divisible by i def countOfWays(arr, N) : # Stores the prefix sum of array pre = [ 0 ] * (N + 1); for i in range(N) : # Find the prefix sum pre[i + 1] = pre[i] + arr[i]; # Initialize dp[][] array dp = np.zeros((N + 2,N + 2)); dp[1][0] += 1; # Stores the count of splitting ans = 0; # Iterate over the range [0, N] for i in range(N) : for j in range(N, 0, -1) : # Update the dp table dp[j + 1][pre[i + 1] % (j + 1)] += dp[j][pre[i + 1] % j]; # If the last index is # reached, then add it # to the variable ans if (i == N - 1) : ans += dp[j][pre[i + 1] % j]; # Return the possible count of # splitting of array into subarrays return ans; # Driver Code if __name__ == "__main__" : arr = [ 1, 2, 3, 4 ]; N = len(arr); print(countOfWays(arr, N)); # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to count ways to split
// an array into subarrays such that
// sum of the i-th subarray is
// divisible by i
static int countOfWays(int[] arr, int N)
{
// Stores the prefix sum of array
int[] pre = new int[N + 1];
for (int i = 0; i < N; i++) {
// Find the prefix sum
pre[i + 1] = pre[i] + arr[i];
}
// Initialize dp[][] array
int[,] dp = new int [N + 2, N + 2];
dp[1, 0]++;
// Stores the count of splitting
int ans = 0;
// Iterate over the range [0, N]
for (int i = 0; i < N; i++) {
for (int j = N; j >= 1; j--) {
// Update the dp table
dp[j + 1, pre[i + 1] % (j + 1)]
+= dp[j, pre[i + 1] % j];
// If the last index is
// reached, then add it
// to the variable ans
if (i == N - 1) {
ans += dp[j, pre[i + 1] % j];
}
}
}
// Return the possible count of
// splitting of array into subarrays
return ans;
}
// Driver Code
public static void Main(String []args) {
int[] arr = { 1, 2, 3, 4 };
int N = arr.Length;
Console.WriteLine(countOfWays(arr, N));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript program for the above approach
// Function to count ways to split
// an array into subarrays such that
// sum of the i-th subarray is
// divisible by i
function countOfWays(arr, N)
{
// Stores the prefix sum of array
let pre = new Array(N + 1).fill(0);
for (let i = 0; i < N; i++)
{
// Find the prefix sum
pre[i + 1] = pre[i] + arr[i];
}
// Initialize dp[][] array
let dp = new Array(N + 2).fill(0).map(() => new Array(N + 2).fill(0));
dp[1][0]++;
// Stores the count of splitting
let ans = 0;
// Iterate over the range [0, N]
for (let i = 0; i < N; i++) {
for (let j = N; j >= 1; j--) {
// Update the dp table
dp[j + 1][pre[i + 1] % (j + 1)] += dp[j][pre[i + 1] % j];
// If the last index is
// reached, then add it
// to the variable ans
if (i == N - 1) {
ans += dp[j][pre[i + 1] % j];
}
}
}
// Return the possible count of
// splitting of array into subarrays
return ans;
}
// Driver Code
let arr = [1, 2, 3, 4];
let N = arr.length;
document.write(countOfWays(arr, N));
// This code is contributed by _Saurabh_Jaiswal
</script>
Producción
3
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por siddhantdugar241 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA