Given a circular array arr[] of N numbers, and an integer K. The task is to print the average for 2K+1 numbers for each elements (K from left, K from right, and the element self).
Examples:
Input: arr []= { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, K = 3
Output: {4.85714, 4.57143, 4.28571, 4.0, 5.0, 6.0, 5.71429, 5.42857, 5.14286}
Explanation: For each value the averages are:
for 1 – right part:9, left part:24 & result:4.85714
for 2 – right part:12, left part:18 & result:4.57143
for 3 – right part:15, left part:12 & result:4.28571
for 4 – right part:18, left part:6 & result:4
for 5 – right part:21, left part:9 & result:5
for 6 – right part:24, left part:12 & result:6
for 7 – right part:18, left part:15 & result:5.71429
for 8 – right part:12, left part:18 & result:5.42857
for 9 – right part:6, left part:21 & result:5.14286Input: arr[] = {2, 2, 2, 2, 2}, K = 3
Output: {2, 2, 2, 2, 2}
Naive Approach: The simplest approach to solve the problem is to traverse the required number of elements for each element of the array. Follow the steps mentioned below:
- Traverse the array and for each element do the following:
- traverse the next K and previous K elements and calculate the mean for these elements.
- Print the answer for each element.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <iostream>using namespace std;// Function to calculate averagevoid average(int arr[], int N, int K){ // Iterate over all elements for (int i = 0; i < N; i++) { int leftSum = 0; int rightSum = 0; // find the right sum for (int j = 1; j <= K; j++) { rightSum += arr[(i + j) % N]; } // Find the leftSum for (int j = 1; j <= K; j++) { leftSum += arr[(i - j < 0 ? i - j + N : i - j) % N]; } // Print mean for each element cout << ((leftSum + rightSum + arr[i]) * 1.0) / (2 * K + 1) << " "; }}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int K = 3; int N = sizeof(arr) / sizeof(int); average(arr, N, K); return 0;} |
Java
// Java code to implement the above approachimport java.util.*;public class GFG{ // Function to calculate averagestatic void average(int[] arr, int N, int K){ // Iterate over all elements for(int i = 0; i < N; i++) { int leftSum = 0; int rightSum = 0; // Find the right sum for(int j = 1; j <= K; j++) { rightSum += arr[(i + j) % N]; } // Find the leftSum for(int j = 1; j <= K; j++) { leftSum += arr[(i - j < 0 ? i - j + N : i - j) % N]; } // Print mean for each element System.out.print( ((leftSum + rightSum + arr[i]) * 1.0) / (2 * K + 1) + " "); }}// Driver codepublic static void main(String args[]){ int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int K = 3; int N = arr.length; average(arr, N, K);}}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code for the above approach# Function to calculate averagedef average(arr, N, K): # Iterate over all elements for i in range(N): leftSum = 0 rightSum = 0 # find the right sum for j in range(1, K + 1): rightSum += arr[(i + j) % N] # Find the leftSum for j in range(1, K + 1): leftSum += arr[((i - j + N) if (i - j < 0) else (i - j)) % N] # Print mean for each element print(round(((leftSum + rightSum + arr[i]) * 1.0) / (2 * K + 1), 5), end=" ") # Driver codearr = [1, 2, 3, 4, 5, 6, 7, 8, 9]K = 3N = len(arr)average(arr, N, K)# This code is contributed by Saurabh Jaiswal |
C#
// C# code to implement the above approachusing System;class GFG{ // Function to calculate averagestatic void average(int[] arr, int N, int K){ // Iterate over all elements for(int i = 0; i < N; i++) { int leftSum = 0; int rightSum = 0; // Find the right sum for(int j = 1; j <= K; j++) { rightSum += arr[(i + j) % N]; } // Find the leftSum for(int j = 1; j <= K; j++) { leftSum += arr[(i - j < 0 ? i - j + N : i - j) % N]; } // Print mean for each element Console.Write( ((leftSum + rightSum + arr[i]) * 1.0) / (2 * K + 1) + " "); }}// Driver codepublic static void Main(){ int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int K = 3; int N = arr.Length; average(arr, N, K);}}// This code is contributed by ukasp |
Javascript
<script> // JavaScript code for the above approach // Function to calculate average function average(arr, N, K) { // Iterate over all elements for (let i = 0; i < N; i++) { let leftSum = 0; let rightSum = 0; // find the right sum for (let j = 1; j <= K; j++) { rightSum += arr[(i + j) % N]; } // Find the leftSum for (let j = 1; j <= K; j++) { leftSum += arr[(i - j < 0 ? i - j + N : i - j) % N]; } // Print mean for each element document.write((((leftSum + rightSum + arr[i]) * 1.0) / (2 * K + 1)).toPrecision(6) + " "); } } // Driver code let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]; let K = 3; let N = arr.length; average(arr, N, K);// This code is contributed by Potta Lokesh </script> |
Output
4.85714 4.57143 4.28571 4 5 6 5.71429 5.42857 5.14286
Time Complexity: O(N*K), as we are using nested loops to traverse N*K times.
Auxiliary Space: O(1), as we are not using any extra space.
Efficient Approach: To reduce the time complexity the concept of prefix sum can be used where prefix sum array(say preSum[]) is calculated like preSum[i] = arr[0] + . . . + arr[i]. And using the preSum[] array the mean can be calculated easily for each elements without traversing (2K + 1) elements in each iterations. Condition for calculating the sum of previous K elements (leftSum) and K next elements (rightSum) for each of the element is given below:
Calculation for sum of K-elements in right:
- If there are K-elements present in right:
rightSum = preSum[i + k] – preSum[i];- If no elements are in right:
rightSum = preSum[k – 1];- If some elements are in right and some needs circular traversal:
eleInRight = n – i – 1;
rightSum = presum[n – 1] – presum[i] + presum[k – eleInRight – 1];Calculation for sum of K-elements in left:
- If there are more than K-elements present in left:
leftSum = preSum[i – 1] – preSum[i – k – 1];- If only k-elements are present in left:
leftSum = preSum[i – 1];- if no elements are in left:
leftSum = preSum[n – 1] – preSum[n – 1 – k];- If some elements are in left and some needs circular traversal:
eleInLeft = i
leftSum = preSum[i – 1] + preSum[n – 1] – preSum[n – 1 – (k – eleInLeft)];
Follow the steps mentioned below to implement it:
- Iterate the array create the prefix sum array.
- For each element get the left and right sum as show in the observation and calculate the average.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the averagevoid average(int arr[], int N, int K){ int presum[N]; presum[0] = arr[0]; for (int i = 1; i < N; i++) { presum[i] = presum[i - 1] + arr[i]; } for (int i = 0; i < N; i++) { // Right part int rightSum = 0; // When all k-elements are // in right if (i + K < N) rightSum = presum[i + K] - presum[i]; else { int eleInRight = N - i - 1; // When some are in right and // some needs circular traversal if (eleInRight > 0) { rightSum = presum[N - 1] - presum[i] + presum[K - eleInRight - 1]; } else { rightSum = presum[K - eleInRight - 1]; } } // Left part int leftSum = 0; // When more than k-elements // are in left if (i - K > 0) leftSum = presum[i - 1] - presum[i - K - 1]; // When exact k-elements are in left else if (i - K == 0) { leftSum = presum[i - 1]; } // When some are in left some // needs circular traversal else { int eleInLeft = i; if (eleInLeft > 0) { leftSum = presum[i - 1] + presum[N - 1] - presum[N - 1 - (K - eleInLeft)]; } else { leftSum = presum[N - 1] - presum[N - 1 - K]; } } cout << ((arr[i] + leftSum + rightSum) * 1.0) / (2 * K + 1) << " "; }}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int K = 3; int N = sizeof(arr) / sizeof(int); average(arr, N, K); return 0;} |
Java
// Java code to implement the above approachimport java.util.*;public class GFG{ // Function to calculate the averagestatic void average(int arr[], int N, int K){ int presum[] = new int[N]; presum[0] = arr[0]; for (int i = 1; i < N; i++) { presum[i] = presum[i - 1] + arr[i]; } for (int i = 0; i < N; i++) { // Right part int rightSum = 0; // When all k-elements are // in right if (i + K < N) rightSum = presum[i + K] - presum[i]; else { int eleInRight = N - i - 1; // When some are in right and // some needs circular traversal if (eleInRight > 0) { rightSum = presum[N - 1] - presum[i] + presum[K - eleInRight - 1]; } else { rightSum = presum[K - eleInRight - 1]; } } // Left part int leftSum = 0; // When more than k-elements // are in left if (i - K > 0) leftSum = presum[i - 1] - presum[i - K - 1]; // When exact k-elements are in left else if (i - K == 0) { leftSum = presum[i - 1]; } // When some are in left some // needs circular traversal else { int eleInLeft = i; if (eleInLeft > 0) { leftSum = presum[i - 1] + presum[N - 1] - presum[N - 1 - (K - eleInLeft)]; } else { leftSum = presum[N - 1] - presum[N - 1 - K]; } } System.out.print(((arr[i] + leftSum + rightSum) * 1.0) / (2 * K + 1) + " "); }}// Driver codepublic static void main(String args[]){ int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int K = 3; int N = arr.length; average(arr, N, K);}}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code to implement the above approach# Function to calculate the averagedef average(arr, N, K): presum = [0]*N presum[0] = arr[0] for i in range(1,N): presum[i] = presum[i - 1] + arr[i] for i in range(0,N): # Right part rightSum = 0 # When all k-elements are # in right if (i + K < N): rightSum = presum[i + K] - presum[i] else: eleInRight = N - i - 1 # When some are in right and # some needs circular traversal if (eleInRight > 0): rightSum = presum[N - 1] - presum[i] + presum[K - eleInRight - 1] else: rightSum = presum[K - eleInRight - 1] # Left part leftSum = 0 # When more than k-elements # are in left if (i - K > 0): leftSum = presum[i - 1] - presum[i - K - 1] # When exact k-elements are in left elif (i - K == 0): leftSum = presum[i - 1] # When some are in left some # needs circular traversal else: eleInLeft = i if (eleInLeft > 0): leftSum = presum[i - 1] + presum[N - 1] - presum[N - 1 - (K - eleInLeft)] else: leftSum = presum[N - 1] - presum[N - 1 - K] print("{:.5f}".format(((arr[i] + leftSum + rightSum) * 1.0) / (2 * K + 1)),end = " ")# Driver codearr = [1, 2, 3, 4, 5, 6, 7, 8, 9]K = 3N = len(arr)average(arr, N, K)# This code is contributed by Shubham Singh |
C#
// C# code to implement the above approachusing System;public class GFG{ // Function to calculate the average static void average(int[] arr, int N, int K) { int[] presum = new int[N]; presum[0] = arr[0]; for (int i = 1; i < N; i++) { presum[i] = presum[i - 1] + arr[i]; } for (int i = 0; i < N; i++) { // Right part int rightSum = 0; // When all k-elements are // in right if (i + K < N) rightSum = presum[i + K] - presum[i]; else { int eleInRight = N - i - 1; // When some are in right and // some needs circular traversal if (eleInRight > 0) { rightSum = presum[N - 1] - presum[i] + presum[K - eleInRight - 1]; } else { rightSum = presum[K - eleInRight - 1]; } } // Left part int leftSum = 0; // When more than k-elements // are in left if (i - K > 0) leftSum = presum[i - 1] - presum[i - K - 1]; // When exact k-elements are in left else if (i - K == 0) { leftSum = presum[i - 1]; } // When some are in left some // needs circular traversal else { int eleInLeft = i; if (eleInLeft > 0) { leftSum = presum[i - 1] + presum[N - 1] - presum[N - 1 - (K - eleInLeft)]; } else { leftSum = presum[N - 1] - presum[N - 1 - K]; } } Console.Write(((arr[i] + leftSum + rightSum) * 1.0) / (2 * K + 1) + " "); } } // Driver code public static void Main() { int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int K = 3; int N = arr.Length; average(arr, N, K); }}// This code is contributed by Shubham Singh |
Javascript
<script> // JavaScript code to implement the above approach // Function to calculate the average const average = (arr, N, K) => { let presum = new Array(N).fill(0); presum[0] = arr[0]; for (let i = 1; i < N; i++) { presum[i] = presum[i - 1] + arr[i]; } for (let i = 0; i < N; i++) { // Right part let rightSum = 0; // When all k-elements are // in right if (i + K < N) rightSum = presum[i + K] - presum[i]; else { let eleInRight = N - i - 1; // When some are in right and // some needs circular traversal if (eleInRight > 0) { rightSum = presum[N - 1] - presum[i] + presum[K - eleInRight - 1]; } else { rightSum = presum[K - eleInRight - 1]; } } // Left part let leftSum = 0; // When more than k-elements // are in left if (i - K > 0) leftSum = presum[i - 1] - presum[i - K - 1]; // When exact k-elements are in left else if (i - K == 0) { leftSum = presum[i - 1]; } // When some are in left some // needs circular traversal else { let eleInLeft = i; if (eleInLeft > 0) { leftSum = presum[i - 1] + presum[N - 1] - presum[N - 1 - (K - eleInLeft)]; } else { leftSum = presum[N - 1] - presum[N - 1 - K]; } } document.write(`${((arr[i] + leftSum + rightSum) * 1.0) / (2 * K + 1)} `); } } // Driver code let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]; let K = 3; let N = arr.length; average(arr, N, K); // This code is contributed by rakeshsahni </script> |
Output
4.85714 4.57143 4.28571 4 5 6 5.71429 5.42857 5.14286
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(N), as we are using extra space for presum.
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!
