Given an array arr[] of size N and an integer K, the task is to print the difference between the maximum and minimum average of the contiguous subarrays of length K.
Examples:
Input: arr[ ] = {3, 8, 9, 15}, K = 2
Output: 6.5
Explanation:
All subarrays of length 2 are {3, 8}, {8, 9}, {9, 15} and their averages are (3+8)/2 = 5.5, (8+9)/2 = 8.5, and (9+15)/2 = 12.0 respectively.
Therefore, the difference between the maximum(=12.0) and minimum(=5.5) is 12.0 -5.5 = 6.5.Input: arr[] = {17, 6.2, 19, 3.4}, K = 3
Output: 4.533
Naive Approach: The simplest approach is to find the average of every contiguous subarray of size K, and then find the maximum and minimum of these values, and print their difference.
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 difference between// averages of the maximum and the minimum// subarrays of length kdouble Avgdifference(double arr[], int N, int K){ // Stores min and max sum double min = 1000000, max = -1; // Iterate through starting points for (int i = 0; i <= N - K; i++) { double sum = 0; // Sum up next K elements for (int j = 0; j < K; j++) { sum += arr[i + j]; } // Update max and min moving sum if (min > sum) min = sum; if (max < sum) max = sum; } // Return the difference between max // and min average return (max - min) / K;}// Driver Codeint main(){ // Given Input double arr[] = { 3, 8, 9, 15 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 2; // Function Call cout << Avgdifference(arr, N, K); return 0;} |
Java
// Java implementation of the above approachimport java.io.*;class GFG{ // Function to find the difference between // averages of the maximum and the minimum // subarrays of length k static double Avgdifference(double arr[], int N, int K) { // Stores min and max sum double min = 1000000, max = -1; // Iterate through starting points for (int i = 0; i <= N - K; i++) { double sum = 0; // Sum up next K elements for (int j = 0; j < K; j++) { sum += arr[i + j]; } // Update max and min moving sum if (min > sum) min = sum; if (max < sum) max = sum; } // Return the difference between max // and min average return (max - min) / K; } // Driver Code public static void main (String[] args) { // Given Input double arr[] = { 3, 8, 9, 15 }; int N =arr.length; int K = 2; // Function Call System.out.println( Avgdifference(arr, N, K)); }}// This code is contributed by Potta Lokesh |
Python3
# Python program for the above approach# Function to find the difference between# averages of the maximum and the minimum# subarrays of length kdef Avgdifference(arr, N, K): # Stores min and max sum min = 1000000; max = -1; # Iterate through starting points for i in range(N - K + 1): sum = 0; # Sum up next K elements for j in range(K): sum += arr[i + j]; # Update max and min moving sum if (min > sum): min = sum; if (max < sum): max = sum; # Return the difference between max # and min average return (max - min) / K;# Driver Code# Given Inputarr = [3, 8, 9, 15];N = len(arr);K = 2;# Function Callprint(Avgdifference(arr, N, K));# This code is contributed by _saurabh_jaiswal. |
C#
// C# program for the above approachusing System;class GFG{// Function to find the difference between// averages of the maximum and the minimum// subarrays of length kstatic double Avgdifference(double []arr, int N, int K){ // Stores min and max sum double min = 1000000, max = -1; // Iterate through starting points for(int i = 0; i <= N - K; i++) { double sum = 0; // Sum up next K elements for(int j = 0; j < K; j++) { sum += arr[i + j]; } // Update max and min moving sum if (min > sum) min = sum; if (max < sum) max = sum; } // Return the difference between max // and min average return(max - min) / K;}// Driver Codepublic static void Main (String[] args) { // Given Input double []arr = { 3, 8, 9, 15 }; int N = arr.Length; int K = 2; // Function Call Console.Write(Avgdifference(arr, N, K));}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript program for the above approach// Function to find the difference between// averages of the maximum and the minimum// subarrays of length kfunction Avgdifference(arr, N, K) { // Stores min and max sum let min = 1000000, max = -1; // Iterate through starting points for (let i = 0; i <= N - K; i++) { let sum = 0; // Sum up next K elements for (let j = 0; j < K; j++) { sum += arr[i + j]; } // Update max and min moving sum if (min > sum) min = sum; if (max < sum) max = sum; } // Return the difference between max // and min average return (max - min) / K;}// Driver Code// Given Inputlet arr = [3, 8, 9, 15];let N = arr.length;let K = 2;// Function Calldocument.write(Avgdifference(arr, N, K));</script> |
Output
6.5
Time Complexity: O(N*K)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using the sliding window technique. Follow the steps below to solve the problem:
- Find the sum of subarrays over the range [0, K-1] and store it in a variable say sum.
- Initialize two variables, say max and min, to store the maximum and minimum sum of any subarray of size K.
- Iterate over the range [K, N-K+1] using the variable i and perform the following steps:
- Remove the element arr[i-K] and add the element arr[i] to the windows of size K. i.e Update sum to sum+arr[i]-arr[i-K].
- Update the min as the minimum of min and sum, and update max as the maximum of max and sum.
- Finally, after completing the above steps, print the answer as (max-min)/K.
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 difference between// the maximum and minimum subarrays of// length Kdouble Avgdifference(double arr[], int N, int K){ // Stores the sum of subarray over the // range [0, K] double sum = 0; // Iterate over the range [0, K] for (int i = 0; i < K; i++) sum += arr[i]; // Store min and max sum double min = sum; double max = sum; // Iterate over the range [K, N-K] for (int i = K; i <= N - K + 1; i++) { // Increment sum by arr[i]-arr[i-K] sum += arr[i] - arr[i - K]; // Update max and min moving sum if (min > sum) min = sum; if (max < sum) max = sum; } // Return difference between max and min // average return (max - min) / K;}// Driver Codeint main(){ // Given Input double arr[] = { 3, 8, 9, 15 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 2; // Function Call cout << Avgdifference(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to find the difference between// the maximum and minimum subarrays of// length Kstatic double Avgdifference(double arr[], int N, int K){ // Stores the sum of subarray over the // range [0, K] double sum = 0; // Iterate over the range [0, K] for(int i = 0; i < K; i++) sum += arr[i]; // Store min and max sum double min = sum; double max = sum; // Iterate over the range [K, N-K] for(int i = K; i <= N - K + 1; i++) { // Increment sum by arr[i]-arr[i-K] sum += arr[i] - arr[i - K]; // Update max and min moving sum if (min > sum) min = sum; if (max < sum) max = sum; } // Return difference between max and min // average return(max - min) / K;}// Driver Codepublic static void main (String[] args) { // Given Input double arr[] = { 3, 8, 9, 15 }; int N = arr.length; int K = 2; // Function Call System.out.println(Avgdifference(arr, N, K));}}// This code is contributed by shivanisinghss2110 |
Python3
# python 3 program for the above approach# Function to find the difference between# the maximum and minimum subarrays of# length Kdef Avgdifference(arr, N, K): # Stores the sum of subarray over the # range [0, K] sum = 0 # Iterate over the range [0, K] for i in range(K): sum += arr[i] # Store min and max sum min = sum max = sum # Iterate over the range [K, N-K] for i in range(K,N - K + 2,1): # Increment sum by arr[i]-arr[i-K] sum += arr[i] - arr[i - K] # Update max and min moving sum if (min > sum): min = sum if (max < sum): max = sum # Return difference between max and min # average return (max - min) / K# Driver Codeif __name__ == '__main__': # Given Input arr = [3, 8, 9, 15] N = len(arr) K = 2 # Function Call print(Avgdifference(arr, N, K)) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;class GFG{// Function to find the difference between// the maximum and minimum subarrays of// length Kstatic double Avgdifference(double []arr, int N, int K){ // Stores the sum of subarray over the // range [0, K] double sum = 0; // Iterate over the range [0, K] for(int i = 0; i < K; i++) sum += arr[i]; // Store min and max sum double min = sum; double max = sum; // Iterate over the range [K, N-K] for(int i = K; i <= N - K + 1; i++) { // Increment sum by arr[i]-arr[i-K] sum += arr[i] - arr[i - K]; // Update max and min moving sum if (min > sum) min = sum; if (max < sum) max = sum; } // Return difference between max and min // average return(max - min) / K;}// Driver Codepublic static void Main (String[] args) { // Given Input double []arr = { 3, 8, 9, 15 }; int N = arr.Length; int K = 2; // Function Call Console.Write(Avgdifference(arr, N, K));}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript program for the above approach// Function to find the difference between// the maximum and minimum subarrays of// length Kfunction Avgdifference(arr, N, K){ // Stores the sum of subarray over the // range [0, K] let sum = 0; // Iterate over the range [0, K] for(let i = 0; i < K; i++) sum += arr[i]; // Store min and max sum let min = sum; let max = sum; // Iterate over the range [K, N-K] for(let i = K; i <= N - K + 1; i++) { // Increment sum by arr[i]-arr[i-K] sum += arr[i] - arr[i - K]; // Update max and min moving sum if (min > sum) min = sum; if (max < sum) max = sum; } // Return difference between max and min // average return(max - min) / K;}// Driver Code // Given Input let arr = [ 3, 8, 9, 15 ]; let N = arr.length; let K = 2; // Function Call document.write(Avgdifference(arr, N, K));// This code is contributed by shivanisinghss2110</script> |
Output
6.5
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
