Find index with minimum difference between prefix and suffix average of given Array

0 0 6 minutes read

Given an array arr[] of size N, the task is to find an index i such that the difference between prefix average and suffix average is minimum, i.e. average of elements till i (in range [0, i]) and the average of elements after i (in range [i+1, N)) is minimum.

Examples:

Input: arr[] = {2, 9, 3, 5}
Output: 0
Explanation:
At index 0,
Average of price till i = 0 is 2 and the average after it is {9, 3, 5} is 17/3 = 5.67.
So the difference of the average till i and after i is -3.67.
At index 1,
Average of price till i = 1 {2, 9} is 11/2 = 5.5 and the average after it is {3, 5} is 8/2 = 4.
So the difference of the average till i and after i is 1.5.
At index 2,
Average of price till i = 2 {2, 9, 3} is 14/3 = 4.67 and the average after it is 5/1 = 5.
So the difference of the average till i and after i is -0.33.
At index 3,
Average of price till i = 3 {2, 9, 3, 5} is 19/4 = 4.75 and the average after it is 0.
So the difference of the average till i and after i is 4.75.
So the minimum value is in index at index 0.

Input: arr[] = {15, 5, 10, 15, 5}
Output: 1

Approach: The problem can be solved based on prefix sum idea as below:

Use prefix sum technique to calculate the average till ith day and the average after the ith day for every index i. Find the day which has the minimum difference of the averages.

Follow these steps to solve the above problem:

Initialize and empty prefix_sum[] array to store the prefix sum.
Traverse through the array and find the prefix sum at every index i.
Initialize the min_day and min_diff = INT_MAX to store the day and the minimum difference.
Traverse through the prefix sum array and calculate the left average and right average and store it in the diff variable.
- Check if the difference is less than min_diff and store update the variable min_diff accordingly.
After processing all, print the min_diff.

Below is the implementation of the above approach:

C++

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

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

Python3

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

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

Javascript

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

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!