Replace all elements of given Array with average of previous K and next K elements
Given an array arr[] containing N positive integers and an integer K. The task is to replace every array element with the average of previous K and next K elements. Also, if K elements are not present then adjust use the maximum number of elements available before and after.
Examples:
Input: arr[] = {9, 7, 3, 9, 1, 8, 11}, K=2
Output: 5 7 6 4 7 7 4
Explanation: For i = 0, average = (7 + 3)/2 = 5
For i = 1, average = (9 + 3 + 9)/3 = 7
For i = 2, average = (9 + 7 + 9 + 1)/4 = 6
For i = 3, average = (7 + 3 + 1 + 8)/4 = 4
For i = 4, average = (3 + 9 + 8 + 11)/4 = 7
For i = 5, average = (9 + 1 + 11)/3 = 7
For i = 6, average = (1 + 8)/2 = 4Input: arr[] = {13, 26, 35, 41, 23, 18, 38}, K=3
Output: 34 28 24 25 31 34 27
Naive Approach: The simplest approach is to use nested loops. The outer loop will traverse the array from left to right, i.e. from i = 0 to i < N and an inner loop will traverse the subarray from index i – K to the index i + K except i and calculate the average of them.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to replace all array elements // with the average of previous and // next K elements void findAverage( int arr[], int N, int K) { int start, end; for ( int i = 0; i < N; i++) { int sum = 0; // Start limit is max(i-K, 0) start = max(i - K, 0); // End limit in min(i+K, N-1) end = min(i + K, N - 1); int cnt = end - start; for ( int j = start; j <= end; j++) { // Skipping the current element if (j == i) { continue ; } sum += arr[j]; } cout << sum / cnt << ' ' ; } } // Driver Code int main() { int arr[] = { 9, 7, 3, 9, 1, 8, 11 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 2; findAverage(arr, N, K); return 0; } |
Java
// Java program to implement // the above approach class GFG { // Function to replace all array elements // with the average of previous and // next K elements static void findAverage( int [] arr, int N, int K) { int start, end; for ( int i = 0 ; i < N; i++) { int sum = 0 ; // Start limit is max(i-K, 0) start = Math.max(i - K, 0 ); // End limit in min(i+K, N-1) end = Math.min(i + K, N - 1 ); int cnt = end - start; for ( int j = start; j <= end; j++) { // Skipping the current element if (j == i) { continue ; } sum += arr[j]; } System.out.print(sum / cnt + " " ); } } // Driver Code public static void main(String[] args) { int [] arr = { 9 , 7 , 3 , 9 , 1 , 8 , 11 }; int N = arr.length; int K = 2 ; findAverage(arr, N, K); } } // This code is contributed by ukasp. |
Python3
# Python code for the above approach # Function to replace all array elements # with the average of previous and # next K elements def findAverage(arr, N, K): start = None end = None for i in range (N): sum = 0 # Start limit is max(i-K, 0) start = max (i - K, 0 ) # End limit in min(i+K, N-1) end = min (i + K, N - 1 ) cnt = end - start for j in range (start, end + 1 ): # Skipping the current element if j = = i: continue sum + = arr[j] print (( sum / / cnt), end = " " ) # Driver Code arr = [ 9 , 7 , 3 , 9 , 1 , 8 , 11 ] N = len (arr) K = 2 findAverage(arr, N, K) # This code is contributed by gfgking |
C#
// C# program to implement // the above approach using System; class GFG { // Function to replace all array elements // with the average of previous and // next K elements static void findAverage( int []arr, int N, int K) { int start, end; for ( int i = 0; i < N; i++) { int sum = 0; // Start limit is max(i-K, 0) start = Math.Max(i - K, 0); // End limit in min(i+K, N-1) end = Math.Min(i + K, N - 1); int cnt = end - start; for ( int j = start; j <= end; j++) { // Skipping the current element if (j == i) { continue ; } sum += arr[j]; } Console.Write(sum / cnt + " " ); } } // Driver Code public static void Main() { int []arr = { 9, 7, 3, 9, 1, 8, 11 }; int N = arr.Length; int K = 2; findAverage(arr, N, K); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to replace all array elements // with the average of previous and // next K elements function findAverage(arr, N, K) { let start, end; for (let i = 0; i < N; i++) { let sum = 0; // Start limit is max(i-K, 0) start = Math.max(i - K, 0); // End limit in min(i+K, N-1) end = Math.min(i + K, N - 1); let cnt = end - start; for (let j = start; j <= end; j++) { // Skipping the current element if (j == i) { continue ; } sum += arr[j]; } document.write(Math.floor(sum / cnt) + ' ' ); } } // Driver Code let arr = [9, 7, 3, 9, 1, 8, 11]; let N = arr.length; let K = 2; findAverage(arr, N, K); // This code is contributed by Potta Lokesh </script> |
5 7 6 4 7 7 4
Time complexity: O(N2)
Auxiliary Space: O(1)
Efficient approach: This approach uses the sliding window method. Follow the steps mentioned below to implement this concept:
- Consider that every element has K next and previous elements and take an window of size 2*K + 1 to cover this whole range.
- Now initially find the sum of first (K+1) elements.
- While traversing the array:
- Calculate the average by dividing the sum with (size of window-1).
- Add the next element after the rightmost end of the current window.
- Remove the leftmost element of the current window. This will shift the window one position to right
- Print the resultant array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to replace all array elements // with the average of previous and // next K elements void findAverage( int arr[], int N, int K) { int i, sum = 0, next, prev, update; int cnt = 0; // Calculate initial sum of K+1 elements for (i = 0; i <= K and i < N; i++) { sum += arr[i]; cnt += 1; } // Using the sliding window technique for (i = 0; i < N; i++) { update = sum - arr[i]; cout << update / (cnt - 1) << " " ; next = i + K + 1; prev = i - K; if (next < N) { sum += arr[next]; cnt += 1; } if (prev >= 0) { sum -= arr[prev]; cnt-=1; } } } // Driver Code int main() { int arr[] = { 9, 7, 3, 9, 1, 8, 11 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 2; findAverage(arr, N, K); return 0; } |
Java
// Java program for the above approach import java.util.*; public class GFG { // Function to replace all array elements // with the average of previous and // next K elements static void findAverage( int arr[], int N, int K) { int i, sum = 0 , next = 0 , prev = 0 , update = 0 ; int cnt = 0 ; // Calculate initial sum of K+1 elements for (i = 0 ; i <= K && i < N; i++) { sum += arr[i]; cnt += 1 ; } // Using the sliding window technique for (i = 0 ; i < N; i++) { update = sum - arr[i]; System.out.print(update / (cnt - 1 ) + " " ); next = i + K + 1 ; prev = i - K; if (next < N) { sum += arr[next]; cnt += 1 ; } if (prev >= 0 ) { sum -= arr[prev]; cnt-= 1 ; } } } // Driver Code public static void main(String[] args) { int arr[] = { 9 , 7 , 3 , 9 , 1 , 8 , 11 }; int N = arr.length; int K = 2 ; findAverage(arr, N, K); } } // This code is contributed by Samim Hossain Mondal |
Python3
# Python program for the above approach # Function to replace all array elements # with the average of previous and # next K elements def findAverage(arr, N, K): sum = 0 ; next = 0 ; prev = 0 ; update = 0 ; cnt = 0 ; # Calculate initial sum of K+1 elements for i in range ( 0 , K + 1 , 1 ): if (i > = N): break sum + = arr[i]; cnt + = 1 ; # Using the sliding window technique for i in range ( 0 , N): update = sum - arr[i]; print (update / / (cnt - 1 ), end = " " ); next = i + K + 1 ; prev = i - K; if ( next < N): sum + = arr[ next ]; cnt + = 1 ; if (prev > = 0 ): sum - = arr[prev]; cnt - = 1 ; # Driver Code if __name__ = = '__main__' : arr = [ 9 , 7 , 3 , 9 , 1 , 8 , 11 ]; N = len (arr); K = 2 ; findAverage(arr, N, K); # This code is contributed by 29AjayKumar |
C#
// C# program for the above approach using System; public class GFG { // Function to replace all array elements // with the average of previous and // next K elements static void findAverage( int []arr, int N, int K) { int i, sum = 0, next = 0, prev = 0, update = 0; int cnt = 0; // Calculate initial sum of K+1 elements for (i = 0; i <= K && i < N; i++) { sum += arr[i]; cnt += 1; } // Using the sliding window technique for (i = 0; i < N; i++) { update = sum - arr[i]; Console.Write(update / (cnt - 1) + " " ); next = i + K + 1; prev = i - K; if (next < N) { sum += arr[next]; cnt += 1; } if (prev >= 0) { sum -= arr[prev]; cnt-=1; } } } // Driver Code public static void Main(String[] args) { int []arr = { 9, 7, 3, 9, 1, 8, 11 }; int N = arr.Length; int K = 2; findAverage(arr, N, K); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the above approach // Function to replace all array elements // with the average of previous and // next K elements const findAverage = (arr, N, K) => { let i, sum = 0, next, prev, update; let cnt = 0; // Calculate initial sum of K+1 elements for (i = 0; i <= K && i < N; i++) { sum += arr[i]; cnt += 1; } // Using the sliding window technique for (i = 0; i < N; i++) { update = sum - arr[i]; document.write(`${parseInt(update / (cnt - 1))} `); next = i + K + 1; prev = i - K; if (next < N) { sum += arr[next]; cnt += 1; } if (prev >= 0) { sum -= arr[prev]; cnt -= 1; } } } // Driver Code let arr = [9, 7, 3, 9, 1, 8, 11]; let N = arr.length; let K = 2; findAverage(arr, N, K); // This code is contributed by rakeshsahni </script> |
5 7 6 4 7 7 4
Time complexity: O(N)
Auxiliary Space: O(1)
Contact Us