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>
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>
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