Encuentre el índice con la diferencia mínima entre el prefijo y el sufijo promedio de la array dada

Dada una array arr[] de tamaño N , la tarea es encontrar un índice i tal que la diferencia entre el promedio del prefijo y el promedio del sufijo sea mínima, es decir, el promedio de elementos hasta i (en el rango [0, i]) y el promedio de elementos después de i (en el rango [i+1, N)) es mínimo.

Ejemplos:

Entrada: arr[] = {2, 9, 3, 5}
Salida: 0
Explicación: 
En el índice 0, el  
    promedio del precio hasta i = 0 es 2 y el promedio después de {9, 3, 5} es 17/3 = 5,67. 
    Entonces, la diferencia del promedio hasta i y después de i es -3.67.
En el índice 1,  
    la media del precio hasta i = 1 {2, 9} es 11/2 = 5,5 y la media después de {3, 5} es 8/2 = 4.
    Entonces, la diferencia de la media hasta i y después yo es 1.5.
En el índice 2,  
    la media del precio hasta i = 2 {2, 9, 3} es 14/3 = 4,67 y la media después es 5/1 = 5. 
    Entonces, la diferencia del promedio hasta i y después de i es -0.33.
En el índice 3, el  
    promedio del precio hasta i = 3 {2, 9, 3, 5} es 19/4 = 4,75 y el promedio posterior es 0. 
    Entonces, la diferencia del promedio hasta i y posterior a i es 4,75.
Entonces, el valor mínimo está en el índice en el índice 0. 

Entrada: arr[] = {15, 5, 10, 15, 5}
Salida: 1

Enfoque: el problema se puede resolver en función de la idea de suma de prefijos de la siguiente manera:

Use la técnica de la suma de prefijos para calcular el promedio hasta el i-ésimo día y el promedio después del i-ésimo día para cada índice i. Encuentre el día que tiene la diferencia mínima de los promedios.

Siga estos pasos para resolver el problema anterior: 

• Inicialice y vacíe la array prefix_sum[] para almacenar la suma del prefijo.
• Recorra la array y encuentre la suma del prefijo en cada índice i.
• Inicialice min_day y min_diff = INT_MAX para almacenar el día y la diferencia mínima.
• Recorra la array de suma de prefijos y calcule el promedio izquierdo y el promedio derecho y guárdelo en la variable diff.
  • Compruebe si la diferencia es menor que min_diff y almacene la actualización de la variable min_diff en consecuencia.
• Después de procesar todo, imprima el min_diff .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the day
// with minimum stock price change
void find_the_day(int arr[], int n)
{
 
    // Initialize and empty prefix_sum array
    int prefix_sum[n];
    prefix_sum[0] = arr[0];
 
    // Find the prefix sum of the array
    for (int i = 1; i < n; i++) {
        prefix_sum[i] = arr[i]
                        + prefix_sum[i - 1];
    }
 
    // Initialize min_diff to store
    // the minimum diff of
    // left_avg and right_avg
    int min_diff = INT_MAX;
 
    // Initialize the min_day to
    // store the day with min price change
    int min_day;
    for (int i = 0; i < n; i++) {
 
        // Calculate left avg till day i
        float left_avg
            = prefix_sum[i] / (i + 1);
        float right_avg;
 
        // Calculate right avg after day i
        if (i == n - 1)
            right_avg = 0;
        else
            right_avg = (prefix_sum[n - 1]
                         - prefix_sum[i])
                        / (n - i - 1);
 
        // Store the price change in the diff
        float diff
            = left_avg - right_avg;
 
        // Store the day with
        // minimum stock price change
        if (diff < min_diff) {
            min_diff = diff;
            min_day = i + 1;
        }
    }
 
    // Print the day
    cout << min_day << endl;
}
 
// Driver code
int main()
{
    int arr[] = { 15, 5, 10, 15, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    find_the_day(arr, N);
    return 0;
}

// JAVA program for the above approach.
import java.util.*;
class GFG
{
   
    // Function to find the day
    // with minimum stock price change
    public static void find_the_day(int arr[], int n)
    {
 
        // Initialize and empty prefix_sum array
        int prefix_sum[] = new int[n];
        prefix_sum[0] = arr[0];
 
        // Find the prefix sum of the array
        for (int i = 1; i < n; i++) {
            prefix_sum[i] = arr[i] + prefix_sum[i - 1];
        }
 
        // Initialize min_diff to store
        // the minimum diff of
        // left_avg and right_avg
        float min_diff = Float.MAX_VALUE;
 
        // Initialize the min_day to
        // store the day with min price change
        int min_day = 0;
        for (int i = 0; i < n; i++) {
 
            // Calculate left avg till day i
            float left_avg = prefix_sum[i] / (i + 1);
            float right_avg;
 
            // Calculate right avg after day i
            if (i == n - 1)
                right_avg = 0;
            else
                right_avg
                    = (prefix_sum[n - 1] - prefix_sum[i])
                      / (n - i - 1);
 
            // Store the price change in the diff
            float diff = left_avg - right_avg;
 
            // Store the day with
            // minimum stock price change
            if (diff < min_diff) {
                min_diff = (float)(diff);
                min_day = i + 1;
            }
        }
 
        // Print the day
        System.out.println(min_day);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 15, 5, 10, 15, 5 };
        int N = arr.length;
 
        // Function call
        find_the_day(arr, N);
    }
}
 
// This code is contributed by Taranpreet

# Python program for the above approach.
 
# Function to find the day
# with minimum stock price change
import sys
 
def find_the_day(arr, n):
 
    # Initialize and empty prefix_sum array
    prefix_sum = [0]*n
    prefix_sum[0] = arr[0]
 
    # Find the prefix sum of the array
    for i in range(1,n):
        prefix_sum[i] = arr[i] + prefix_sum[i - 1]
 
    # Initialize min_diff to store
    # the minimum diff of
    # left_avg and right_avg
    min_diff = sys.maxsize
 
    # Initialize the min_day to
    # store the day with min price change
    for i in range(n):
 
        # Calculate left avg till day i
        left_avg = prefix_sum[i] / (i + 1)
 
        # Calculate right avg after day i
        if (i == n - 1):
            right_avg = 0
        else:
            right_avg = (prefix_sum[n - 1]
                         - prefix_sum[i])/ (n - i - 1)
 
        # Store the price change in the diff
        diff = left_avg - right_avg
 
        # Store the day with
        # minimum stock price change
        if (diff < min_diff):
            min_diff = diff
            min_day = i + 1
 
    # Print the day
    print(min_day)
 
# Driver code
 
arr = [ 15, 5, 10, 15, 5 ]
N = len(arr)
 
# Function call
find_the_day(arr, N)
 
# This code is contributed by shinjanpatra

// C# program for the above approach.
using System;
class GFG
{
 
  // Function to find the day
  // with minimum stock price change
  static void find_the_day(int []arr, int n)
  {
 
    // Initialize and empty prefix_sum array
    int []prefix_sum = new int[n];
    prefix_sum[0] = arr[0];
 
    // Find the prefix sum of the array
    for (int i = 1; i < n; i++) {
      prefix_sum[i] = arr[i] + prefix_sum[i - 1];
    }
 
    // Initialize min_diff to store
    // the minimum diff of
    // left_avg and right_avg
    float min_diff = Single.MaxValue;
 
    // Initialize the min_day to
    // store the day with min price change
    int min_day = 0;
    for (int i = 0; i < n; i++) {
 
      // Calculate left avg till day i
      float left_avg = prefix_sum[i] / (i + 1);
      float right_avg;
 
      // Calculate right avg after day i
      if (i == n - 1)
        right_avg = 0;
      else
        right_avg
        = (prefix_sum[n - 1] - prefix_sum[i])
        / (n - i - 1);
 
      // Store the price change in the diff
      float diff = left_avg - right_avg;
 
      // Store the day with
      // minimum stock price change
      if (diff < min_diff) {
        min_diff = (float)(diff);
        min_day = i + 1;
      }
    }
 
    // Print the day
    Console.WriteLine(min_day);
  }
 
  // Driver code
  public static void Main()
  {
    int []arr = { 15, 5, 10, 15, 5 };
    int N = arr.Length;
 
    // Function call
    find_the_day(arr, N);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
 
// JavaScript program for the above approach.
 
// Function to find the day
// with minimum stock price change
function find_the_day(arr, n)
{
 
    // Initialize and empty prefix_sum array
    let prefix_sum = new Array(n);
    prefix_sum[0] = arr[0];
 
    // Find the prefix sum of the array
    for (let i = 1; i < n; i++) {
        prefix_sum[i] = arr[i]
                        + prefix_sum[i - 1];
    }
 
    // Initialize min_diff to store
    // the minimum diff of
    // left_avg and right_avg
    let min_diff = Number.MAX_VALUE
 
    // Initialize the min_day to
    // store the day with min price change
    let min_day;
    for (let i = 0; i <n ; i++) {
 
        // Calculate left avg till day i
        let left_avg
            = prefix_sum[i] / (i + 1);
        let right_avg;
 
        // Calculate right avg after day i
        if (i == n - 1)
            right_avg = 0;
        else
            right_avg = (prefix_sum[n - 1]
                         - prefix_sum[i])
                        / (n - i - 1);
 
        // Store the price change in the diff
        let diff
            = left_avg - right_avg;
 
        // Store the day with
        // minimum stock price change
        if (diff < min_diff) {
            min_diff = diff;
            min_day = i + 1;
        }
    }
 
    // Print the day
    document.write(min_day,"</br>");
}
 
// Driver code
let arr = [ 15, 5, 10, 15, 5 ];
let N = arr.length;
 
// Function call
find_the_day(arr, N);
 
// This code is contributed by shinjanpatra
 
</script>

2

Complejidad temporal: O(N)
Espacio auxiliar: O(N)