Dada una array A[] que consta de N enteros de un rango [1, N] , la tarea es calcular el recuento de elementos de array (no distintos) que se pueden representar como la suma de dos o más elementos de array consecutivos.
Ejemplos:
Entrada: a[] = {3, 1, 4, 1, 5, 9, 2, 6, 5}
Salida: 5
Explicación:
Los elementos del arreglo que satisfacen la condición son:
4 = 3 + 1
5 = 1 + 4 o 4 + 1
9 = 3 + 1 + 4 + 1
6 = 1 + 5 o 1 + 4 + 1
5 = 1 + 4 o 4 + 1Entrada: a[] = {1, 1, 1, 1, 1}
Salida: 0
Explicación:
No existe ningún elemento de array que pueda representarse como la suma de dos o más elementos consecutivos.
Enfoque ingenuo: recorra la array dada para cada elemento, encuentre la suma de todos los subarreglos posibles y verifique si la suma de cualquiera de los subarreglos es igual a la del elemento actual. Aumente el recuento si se determina que es cierto. Finalmente, imprima el conteo obtenido.
Tiempo Complejidad: O(n 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: siga los pasos a continuación para optimizar el enfoque anterior:
- Inicialice una array cnt[] para almacenar el número de ocurrencias de cada elemento de la array.
- Iterar sobre todos los subarreglos de al menos una longitud de 2 manteniendo la suma de la suma del subarreglo actual.
- Si la suma actual no excede N , agregue cnt[sum] a la respuesta y establezca cnt[sum]=0 para evitar contar los mismos elementos varias veces.
- Finalmente, imprima la suma obtenida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the number of
// array elements that can be
// represented as the sum of two
// or more consecutive array elements
int countElements(int a[], int n)
{
// Stores the frequencies
// of array elements
int cnt[n + 1] = {0};
memset(cnt, 0, sizeof(cnt));
// Stores required count
int ans = 0;
// Update frequency of
// each array element
for(int i = 0; i < n; i++)
{
++cnt[a[i]];
}
// Find sum of all subarrays
for(int l = 0; l < n; ++l)
{
int sum = 0;
for(int r = l; r < n; ++r)
{
sum += a[r];
if (l == r)
continue;
if (sum <= n)
{
// Increment ans by cnt[sum]
ans += cnt[sum];
// Reset cnt[sum] by 0
cnt[sum] = 0;
}
}
}
// Return ans
return ans;
}
// Driver Code
int main()
{
// Given array
int a[] = { 1, 1, 1, 1, 1 };
int N = sizeof(a) / sizeof(a[0]);
// Function call
cout << countElements(a, N);
}
// This code is contributed by Amit Katiyar
Java
// Java Program for above approach
import java.util.*;
class GFG {
// Function to find the number of array
// elements that can be represented as the sum
// of two or more consecutive array elements
static int countElements(int[] a, int n)
{
// Stores the frequencies
// of array elements
int[] cnt = new int[n + 1];
// Stores required count
int ans = 0;
// Update frequency of
// each array element
for (int k : a) {
++cnt[k];
}
// Find sum of all subarrays
for (int l = 0; l < n; ++l) {
int sum = 0;
for (int r = l; r < n; ++r) {
sum += a[r];
if (l == r)
continue;
if (sum <= n) {
// Increment ans by cnt[sum]
ans += cnt[sum];
// Reset cnt[sum] by 0
cnt[sum] = 0;
}
}
}
// Return ans
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array
int[] a = { 1, 1, 1, 1, 1 };
// Function call
System.out.println(
countElements(a, a.length));
}
}
Python3
# Python3 program for above approach # Function to find the number of array # elements that can be represented as the sum # of two or more consecutive array elements def countElements(a, n): # Stores the frequencies # of array elements cnt = [0] * (n + 1) # Stores required count ans = 0 # Update frequency of # each array element for k in a: cnt[k] += 1 # Find sum of all subarrays for l in range(n): sum = 0 for r in range(l, n): sum += a[r] if (l == r): continue if (sum <= n): # Increment ans by cnt[sum] ans += cnt[sum] # Reset cnt[sum] by 0 cnt[sum] = 0 # Return ans return ans # Driver Code if __name__ == '__main__': # Given array a = [ 1, 1, 1, 1, 1 ] # Function call print(countElements(a, len(a))) # This code is contributed by mohit kumar 29
C#
// C# program for above approach
using System;
class GFG{
// Function to find the number of array
// elements that can be represented as the sum
// of two or more consecutive array elements
static int countElements(int[] a, int n)
{
// Stores the frequencies
// of array elements
int[] cnt = new int[n + 1];
// Stores required count
int ans = 0;
// Update frequency of
// each array element
foreach(int k in a)
{
++cnt[k];
}
// Find sum of all subarrays
for(int l = 0; l < n; ++l)
{
int sum = 0;
for(int r = l; r < n; ++r)
{
sum += a[r];
if (l == r)
continue;
if (sum <= n)
{
// Increment ans by cnt[sum]
ans += cnt[sum];
// Reset cnt[sum] by 0
cnt[sum] = 0;
}
}
}
// Return ans
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int[] a = { 1, 1, 1, 1, 1 };
// Function call
Console.WriteLine(countElements(a, a.Length));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for above approach
// Function to find the number of array
// elements that can be represented as the sum
// of two or more consecutive array elements
function countElements(a, n)
{
// Stores the frequencies
// of array elements
var cnt = Array(n + 1).fill(0);
// Stores required count
var ans = 0;
// Update frequency of
// each array element
for(k = 0; k < n; k++)
{
cnt[a[k]]++;
}
// Find sum of all subarrays
for(l = 0; l < n; ++l)
{
var sum = 0;
for(r = l; r < n; ++r)
{
sum += a[r];
if (l == r)
continue;
if (sum <= n)
{
// Increment ans by cnt[sum]
ans += cnt[sum];
// Reset cnt[sum] by 0
cnt[sum] = 0;
}
}
}
// Return ans
return ans;
}
// Driver Code
// Given array
var a = [ 1, 1, 1, 1, 1 ];
// Function call
document.write(countElements(a, a.length));
// This code is contributed by todaysgaurav
</script>
Producción:
0
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)