Cuente el subarreglo con una suma estrictamente mayor que la suma de los elementos restantes

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:
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} = 6

Entrada: arr[] = {10, 9, 12, 6} 
Salida:
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.

  1. El primer bucle indica el comienzo del subarreglo.
  2. El segundo bucle indica el final del subarreglo.
  3. Dentro del segundo bucle, tenemos bucles for para calcular subarray_sum y la suma restante de los elementos de la array.
  4. 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. 

  1. Se calcula la suma total de la array dada.
  2. Ejecute un ciclo for donde la variable de ciclo i indique el índice inicial del subarreglo.
  3. Otro ciclo, donde cada j indica el índice final del subarreglo y calcula subarray_sum para cada j-ésimo índice.
  4. subarray_sum=arr[i]+arr[i+1]+…..+arr[j] 
    restante_sum=total_sum – subarray_sum
  5. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *