Dado un arreglo arr[] de N enteros positivos, la tarea es contar todos los subarreglos donde la suma de los elementos del subarreglo es estrictamente mayor que la suma de los elementos restantes.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 6
Explicación:
Los subarreglos son:
{1, 2, 3, 4} – suma del subarreglo = 10, suma de los elementos restantes {5} = 5
{1, 2, 3, 4, 5} – suma del subarreglo = 15, suma del elemento restante = 0
{2, 3, 4} – suma del subarreglo = 9, suma de los elementos restantes {1, 5} = 6
{ 2, 3, 4, 5} – suma del subarreglo = 14, suma de los elementos restantes {1} = 1
{3, 4, 5} – suma del subarreglo = 12, suma de los elementos restantes {1, 2} = 3
{ 4, 5} – suma de subarreglo = 9, suma de elementos restantes {1, 2, 3} = 6Entrada: arr[] = {10, 9, 12, 6}
Salida: 5
Explicación:
Los subarreglos son:
{10, 9} – suma del subarreglo = 19, suma de los elementos restantes {12, 6} = 18
{10, 9, 12} – suma de subarreglo = 31, suma de elementos restantes {6} = 6
{10, 9, 12, 6} – suma de subarreglo = 37, suma de elementos restantes = 0
{9, 12} – suma de subarreglo = 21, suma de elementos restantes {10, 6} = 16
{9, 12, 6} – suma de subarreglo = 27, suma de elementos restantes {10} = 10
Enfoque ingenuo:
un enfoque ingenuo es generar la suma de cada subarreglo utilizando tres bucles anidados y verificar la suma del subarreglo calculado con la suma de los elementos restantes del arreglo.
- El primer bucle indica el comienzo del subarreglo.
- El segundo bucle indica el final del subarreglo.
- Dentro del segundo bucle, tenemos bucles for para calcular subarray_sum y la suma restante de los elementos de la array.
- Incrementa el contador, cuando subarray_sum es estrictamente mayor que resting_sum.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of
// sub-arrays with sum strictly greater
// than the remaining elements of array
int Count_subarray(int arr[], int n)
{
int subarray_sum, remaining_sum, count = 0;
// For loop for beginning point of a subarray
for (int i = 0; i < n; i++) {
// For loop for ending point of the subarray
for (int j = i; j < n; j++) {
// Initialise subarray_sum and
// remaining_sum to 0
subarray_sum = 0;
remaining_sum = 0;
// For loop to calculate
// the sum of generated subarray
for (int k = i; k <= j; k++) {
subarray_sum += arr[k];
}
// For loop to calculate the
// sum remaining array element
for (int l = 0; l < i; l++) {
remaining_sum += arr[l];
}
for (int l = j + 1; l < n; l++) {
remaining_sum += arr[l];
}
// Checking for condition when
// subarray sum is strictly greater than
// remaining sum of array element
if (subarray_sum > remaining_sum) {
count += 1;
}
}
}
return count;
}
// Driver code
int main()
{
int arr[] = { 10, 9, 12, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << Count_subarray(arr, n);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
// Function to count the number of
// sub-arrays with sum strictly greater
// than the remaining elements of array
static int Count_subarray(int arr[], int n)
{
int subarray_sum, remaining_sum, count = 0;
// For loop for beginning point of a subarray
for (int i = 0; i < n; i++)
{
// For loop for ending point of the subarray
for (int j = i; j < n; j++)
{
// Initialise subarray_sum and
// remaining_sum to 0
subarray_sum = 0;
remaining_sum = 0;
// For loop to calculate
// the sum of generated subarray
for (int k = i; k <= j; k++)
{
subarray_sum += arr[k];
}
// For loop to calculate the
// sum remaining array element
for (int l = 0; l < i; l++)
{
remaining_sum += arr[l];
}
for (int l = j + 1; l < n; l++)
{
remaining_sum += arr[l];
}
// Checking for condition when
// subarray sum is strictly greater than
// remaining sum of array element
if (subarray_sum > remaining_sum)
{
count += 1;
}
}
}
return count;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 10, 9, 12, 6 };
int n = arr.length;
System.out.print(Count_subarray(arr, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python implementation of the above approach # Function to count the number of # sub-arrays with sum strictly greater # than the remaining elements of array def Count_subarray(arr, n): subarray_sum, remaining_sum, count = 0, 0, 0; # For loop for beginning point of a subarray for i in range(n): # For loop for ending point of the subarray for j in range(i, n): # Initialise subarray_sum and # remaining_sum to 0 subarray_sum = 0; remaining_sum = 0; # For loop to calculate # the sum of generated subarray for k in range(i, j + 1): subarray_sum += arr[k]; # For loop to calculate the # sum remaining array element for l in range(i): remaining_sum += arr[l]; for l in range(j + 1, n): remaining_sum += arr[l]; # Checking for condition when # subarray sum is strictly greater than # remaining sum of array element if (subarray_sum > remaining_sum): count += 1; return count; # Driver code if __name__ == '__main__': arr = [ 10, 9, 12, 6]; n = len(arr); print(Count_subarray(arr, n)); # This code is contributed by 29AjayKumar
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to count the number of
// sub-arrays with sum strictly greater
// than the remaining elements of array
static int Count_subarray(int []arr, int n)
{
int subarray_sum, remaining_sum, count = 0;
// For loop for beginning point of a subarray
for (int i = 0; i < n; i++)
{
// For loop for ending point of the subarray
for (int j = i; j < n; j++)
{
// Initialise subarray_sum and
// remaining_sum to 0
subarray_sum = 0;
remaining_sum = 0;
// For loop to calculate
// the sum of generated subarray
for (int k = i; k <= j; k++)
{
subarray_sum += arr[k];
}
// For loop to calculate the
// sum remaining array element
for (int l = 0; l < i; l++)
{
remaining_sum += arr[l];
}
for (int l = j + 1; l < n; l++)
{
remaining_sum += arr[l];
}
// Checking for condition when
// subarray sum is strictly greater than
// remaining sum of array element
if (subarray_sum > remaining_sum)
{
count += 1;
}
}
}
return count;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 10, 9, 12, 6 };
int n = arr.Length;
Console.Write(Count_subarray(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of
// the above approach
// Function to count the number of
// sub-arrays with sum strictly greater
// than the remaining elements of array
function Count_subarray(arr, n)
{
var subarray_sum, remaining_sum,
count = 0;
var i,j,k,l;
// For loop for beginning
// point of a subarray
for(i = 0; i < n; i++) {
// For loop for ending point
// of the subarray
for (j = i; j < n; j++) {
// Initialise subarray_sum and
// remaining_sum to 0
subarray_sum = 0;
remaining_sum = 0;
// For loop to calculate
// the sum of generated subarray
for(k = i; k <= j; k++) {
subarray_sum += arr[k];
}
// For loop to calculate the
// sum remaining array element
for (l = 0; l < i; l++) {
remaining_sum += arr[l];
}
for (l = j + 1; l < n; l++) {
remaining_sum += arr[l];
}
// Checking for condition when
// subarray sum is strictly
// greater than
// remaining sum of array element
if (subarray_sum > remaining_sum)
{
count += 1;
}
}
}
return count;
}
// Driver code
var arr = [10, 9, 12, 6];
var n = arr.length;
document.write(Count_subarray(arr, n));
</script>
Producción:
5
Complejidad temporal: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente:
una solución eficiente es utilizar la suma total de la array dada arr[] que ayuda a calcular la suma_subarray y la suma_restante.
- Se calcula la suma total de la array dada.
- Ejecute un ciclo for donde la variable de ciclo i indique el índice inicial del subarreglo.
- Otro ciclo, donde cada j indica el índice final del subarreglo y calcula subarray_sum para cada j-ésimo índice.
- subarray_sum=arr[i]+arr[i+1]+…..+arr[j]
restante_sum=total_sum – subarray_sum - Luego, verifique la condición y el contador de incrementos cuando la suma del subarreglo sea estrictamente mayor que la suma restante de los elementos del arreglo.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
int Count_subarray(int arr[], int n)
{
int total_sum = 0, subarray_sum,
remaining_sum, count = 0;
// Calculating total sum of given array
for (int i = 0; i < n; i++) {
total_sum += arr[i];
}
// For loop for beginning point of a subarray
for (int i = 0; i < n; i++) {
// initialise subarray_sum to 0
subarray_sum = 0;
// For loop for calculating
// subarray_sum and remaining_sum
for (int j = i; j < n; j++) {
// Calculating subarray_sum
// and corresponding remaining_sum
subarray_sum += arr[j];
remaining_sum = total_sum - subarray_sum;
// Checking for the condition when
// subarray sum is strictly greater than
// the remaining sum of the array element
if (subarray_sum > remaining_sum) {
count += 1;
}
}
}
return count;
}
// Driver code
int main()
{
int arr[] = { 10, 9, 12, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << Count_subarray(arr, n);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
static int Count_subarray(int arr[], int n)
{
int total_sum = 0, subarray_sum,
remaining_sum, count = 0;
// Calculating total sum of given array
for (int i = 0; i < n; i++)
{
total_sum += arr[i];
}
// For loop for beginning point of a subarray
for (int i = 0; i < n; i++)
{
// initialise subarray_sum to 0
subarray_sum = 0;
// For loop for calculating
// subarray_sum and remaining_sum
for (int j = i; j < n; j++)
{
// Calculating subarray_sum
// and corresponding remaining_sum
subarray_sum += arr[j];
remaining_sum = total_sum - subarray_sum;
// Checking for the condition when
// subarray sum is strictly greater than
// the remaining sum of the array element
if (subarray_sum > remaining_sum)
{
count += 1;
}
}
}
return count;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 10, 9, 12, 6 };
int n = arr.length;
System.out.print(Count_subarray(arr, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the above approach def Count_subarray(arr, n) : total_sum = 0; count = 0; # Calculating total sum of given array for i in range(n) : total_sum += arr[i]; # For loop for beginning point of a subarray for i in range(n) : # initialise subarray_sum to 0 subarray_sum = 0; # For loop for calculating # subarray_sum and remaining_sum for j in range(i, n) : # Calculating subarray_sum # and corresponding remaining_sum subarray_sum += arr[j]; remaining_sum = total_sum - subarray_sum; # Checking for the condition when # subarray sum is strictly greater than # the remaining sum of the array element if (subarray_sum > remaining_sum) : count += 1; return count; # Driver code if __name__ == "__main__" : arr = [ 10, 9, 12, 6 ]; n = len(arr); print(Count_subarray(arr, n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the above approach
using System;
class GFG
{
static int Count_subarray(int []arr, int n)
{
int total_sum = 0, subarray_sum,
remaining_sum, count = 0;
// Calculating total sum of given array
for (int i = 0; i < n; i++)
{
total_sum += arr[i];
}
// For loop for beginning point of a subarray
for (int i = 0; i < n; i++)
{
// initialise subarray_sum to 0
subarray_sum = 0;
// For loop for calculating
// subarray_sum and remaining_sum
for (int j = i; j < n; j++)
{
// Calculating subarray_sum
// and corresponding remaining_sum
subarray_sum += arr[j];
remaining_sum = total_sum - subarray_sum;
// Checking for the condition when
// subarray sum is strictly greater than
// the remaining sum of the array element
if (subarray_sum > remaining_sum)
{
count += 1;
}
}
}
return count;
}
// Driver code
public static void Main()
{
int []arr = { 10, 9, 12, 6 };
int n = arr.Length;
Console.WriteLine(Count_subarray(arr, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// javascript implementation of the above approach
function Count_subarray(arr, n)
{
var total_sum = 0, subarray_sum, remaining_sum, count = 0;
// Calculating total sum of given array
for (i = 0; i < n; i++)
{
total_sum += arr[i];
}
// For loop for beginning point of a subarray
for (i = 0; i < n; i++)
{
// initialise subarray_sum to 0
subarray_sum = 0;
// For loop for calculating
// subarray_sum and remaining_sum
for (j = i; j < n; j++)
{
// Calculating subarray_sum
// and corresponding remaining_sum
subarray_sum += arr[j];
remaining_sum = total_sum - subarray_sum;
// Checking for the condition when
// subarray sum is strictly greater than
// the remaining sum of the array element
if (subarray_sum > remaining_sum)
{
count += 1;
}
}
}
return count;
}
// Driver code
var arr = [ 10, 9, 12, 6 ];
var n = arr.length;
document.write(Count_subarray(arr, n));
// This code is contributed by todaysgaurav
</script>
Producción:
5
Complejidad del tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Chauhanvishesh99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA