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 changevoid 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 codeint 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 changeimport sysdef 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 codearr = [ 15, 5, 10, 15, 5 ]N = len(arr)# Function callfind_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 changefunction 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 codelet arr = [ 15, 5, 10, 15, 5 ];let N = arr.length;// Function callfind_the_day(arr, N);// This code is contributed by shinjanpatra</script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
