Dada una array de enteros arr[] , la tarea es contar el número de subarreglos de modo que el promedio de elementos presentes en el subarreglo sea mayor que el promedio de elementos que no están presentes en el subarreglo.
Ejemplos:
Entrada: arr[] = {6, 3, 5}
Salida: 3
Los sub-arreglos son {6}, {5} y {6, 3, 5} porque sus promedios
son mayores que {3, 5}, {6 , 3} y {} respectivamente.
Entrada: arr[] = {2, 1, 4, 1}
Salida: 5
Enfoque: el problema se puede resolver fácilmente calculando la array de suma de prefijos de la array dada. El i-ésimo elemento de la array de suma de prefijos contendrá la suma de elementos hasta i . Entonces, la suma de elementos entre dos índices i y j se puede encontrar usando la array de suma de prefijos. Usando un bucle anidado, encuentre todos los subconjuntos posibles de modo que su suma promedio sea mayor que el promedio de los elementos que no están presentes en el conjunto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of sub-arrays
// such that the average of elements present
// in the sub-array is greater than the
// average of the elements not present
// in the sub-array
int countSubarrays(int a[], int n)
{
// Initialize the count variable
int count = 0;
// Initialize prefix sum array
int pre[n + 1] = { 0 };
// Preprocessing prefix sum
for (int i = 1; i < n + 1; i++) {
pre[i] = pre[i - 1] + a[i - 1];
}
for (int i = 1; i < n + 1; i++) {
for (int j = i; j < n + 1; j++) {
// Calculating sum and count
// to calculate averages
int sum1 = pre[j] - pre[i - 1], count1 = j - i + 1;
int sum2 = pre[n] - sum1, count2 = ((n - count1) == 0) ? 1 : (n - count1);
// Calculating averages
int includ = sum1 / count1;
int exclud = sum2 / count2;
// Increment count if including avg
// is greater than excluding avg
if (includ > exclud)
count++;
}
}
return count;
}
// Driver code
int main()
{
int arr[] = { 6, 3, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countSubarrays(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the count of sub-arrays
// such that the average of elements present
// in the sub-array is greater than the
// average of the elements not present
// in the sub-array
static int countSubarrays(int a[], int n)
{
// Initialize the count variable
int count = 0;
// Initialize prefix sum array
int []pre = new int[n + 1];
Arrays.fill(pre, 0);
// Preprocessing prefix sum
for (int i = 1; i < n + 1; i++)
{
pre[i] = pre[i - 1] + a[i - 1];
}
for (int i = 1; i < n + 1; i++)
{
for (int j = i; j < n + 1; j++)
{
// Calculating sum and count
// to calculate averages
int sum1 = pre[j] - pre[i - 1], count1 = j - i + 1;
int sum2 = pre[n] - sum1, count2 =
((n - count1) == 0) ? 1 : (n - count1);
// Calculating averages
int includ = sum1 / count1;
int exclud = sum2 / count2;
// Increment count if including avg
// is greater than excluding avg
if (includ > exclud)
count++;
}
}
return count;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 6, 3, 5 };
int n = arr.length;
System.out.println(countSubarrays(arr, n));
}
}
// This code is contributed by SURENDRA_GANGWAR
Python3
# Python3 implementation of the approach # Function to return the count of sub-arrays # such that the average of elements present # in the sub-array is greater than the # average of the elements not present # in the sub-array def countSubarrays(a, n): # Initialize the count variable count = 0 # Initialize prefix sum array pre = [0 for i in range(n + 1)] # Preprocessing prefix sum for i in range(1, n + 1): pre[i] = pre[i - 1] + a[i - 1] for i in range(1, n + 1): for j in range(i, n + 1): # Calculating sum and count # to calculate averages sum1 = pre[j] - pre[i - 1] count1 = j - i + 1 sum2 = pre[n] - sum1 if n-count1 == 0: count2 = 1 else: count2 = n - count1 # Calculating averages includ = sum1 // count1 exclud = sum2 // count2 # Increment count if including avg # is greater than excluding avg if (includ > exclud): count += 1 return count # Driver code arr = [6, 3, 5 ] n = len(arr) print(countSubarrays(arr, n)) # This code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count of sub-arrays
// such that the average of elements present
// in the sub-array is greater than the
// average of the elements not present
// in the sub-array
static int countSubarrays(int []a, int n)
{
// Initialize the count variable
int count = 0;
// Initialize prefix sum array
int []pre = new int[n + 1];
Array.Fill(pre, 0);
// Preprocessing prefix sum
for (int i = 1; i < n + 1; i++)
{
pre[i] = pre[i - 1] + a[i - 1];
}
for (int i = 1; i < n + 1; i++)
{
for (int j = i; j < n + 1; j++)
{
// Calculating sum and count
// to calculate averages
int sum1 = pre[j] - pre[i - 1], count1 = j - i + 1;
int sum2 = pre[n] - sum1, count2 =
((n - count1) == 0) ? 1 : (n - count1);
// Calculating averages
int includ = sum1 / count1;
int exclud = sum2 / count2;
// Increment count if including avg
// is greater than excluding avg
if (includ > exclud)
count++;
}
}
return count;
}
// Driver code
public static void Main()
{
int []arr = { 6, 3, 5 };
int n = arr.Length;
Console.WriteLine(countSubarrays(arr, n));
}
}
// This code is contributed by Akanksha Rai
PHP
<?php
// PHP implementation of the approach
// Function to return the count of sub-arrays
// such that the average of elements present
// in the sub-array is greater than the
// average of the elements not present
// in the sub-array
function countSubarrays($a, $n)
{
// Initialize the count variable
$count = 0;
// Initialize prefix sum array
$pre = array_fill(0, $n + 1, 0);
// Preprocessing prefix sum
for ($i = 1; $i < $n + 1; $i++)
{
$pre[$i] = $pre[$i - 1] + $a[$i - 1];
}
for ($i = 1; $i < $n + 1; $i++)
{
for ($j = $i; $j < $n + 1; $j++)
{
// Calculating sum and count
// to calculate averages
$sum1 = $pre[$j] - $pre[$i - 1] ;
$count1 = $j - $i + 1;
$sum2 = $pre[$n] - $sum1;
$count2 = (($n - $count1) == 0) ?
1 : ($n - $count1);
// Calculating averages
$includ = floor($sum1 / $count1);
$exclud = floor($sum2 / $count2);
// Increment count if including avg
// is greater than excluding avg
if ($includ > $exclud)
$count++;
}
}
return $count;
}
// Driver code
$arr = array( 6, 3, 5 );
$n = count($arr) ;
echo countSubarrays($arr, $n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the count of sub-arrays
// such that the average of elements present
// in the sub-array is greater than the
// average of the elements not present
// in the sub-array
function countSubarrays(a, n)
{
// Initialize the count variable
let count = 0;
// Initialize prefix sum array
let pre = new Uint8Array(n + 1);
// Preprocessing prefix sum
for (let i = 1; i < n + 1; i++) {
pre[i] = pre[i - 1] + a[i - 1];
}
for (let i = 1; i < n + 1; i++) {
for (let j = i; j < n + 1; j++) {
// Calculating sum and count
// to calculate averages
let sum1 = pre[j] - pre[i - 1], count1 = j - i + 1;
let sum2 = pre[n] - sum1, count2 = ((n - count1) == 0) ? 1 : (n - count1);
// Calculating averages
let includ = Math.floor(sum1 / count1);
let exclud = Math.floor(sum2 / count2);
// Increment count if including avg
// is greater than excluding avg
if (includ > exclud)
count++;
}
}
return count;
}
// Driver code
let arr = [ 6, 3, 5 ];
let n = arr.length;
document.write(countSubarrays(arr, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
3
Complejidad de tiempo: O (N ^ 2) donde N es la longitud de la array, ya que se utilizan bucles anidados para atravesar N * N veces.
Espacio auxiliar: O (N), ya que estamos usando una array previa de tamaño N mientras que es espacio adicional.
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA