Dada una array circular arr[] de N números y un número entero K . La tarea es imprimir el promedio de 2K+1 números para cada elemento (K desde la izquierda, K desde la derecha y el propio elemento).
Ejemplos:
Entrada: arr []= { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, K = 3
Salida: {4.85714, 4.57143, 4.28571, 4.0, 5.0, 6.0, 5.71429, 5.42857, 5.14286}
Explicación: Para cada valor, los promedios son:
para 1 – parte derecha: 9, parte izquierda: 24 y resultado: 4,85714
para 2 – parte derecha: 12, parte izquierda: 18 y resultado: 4,57143
para 3 – parte derecha: 15, izquierda parte:12 y resultado:4.28571
para 4 – parte derecha:18, parte izquierda:6 y resultado:4
para 5 – parte derecha:21, parte izquierda:9 y resultado:5
para 6 – parte derecha:24, parte izquierda: 12 y resultado: 6
para 7 – parte derecha: 18, parte izquierda: 15 y resultado: 5,71429
para 8 – parte derecha: 12, parte izquierda: 18 y resultado: 5,42857
para 9 – parte derecha: 6, parte izquierda: 21 y resultado: 5.14286Entrada: arr[] = {2, 2, 2, 2, 2}, K = 3
Salida: {2, 2, 2, 2, 2}
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar el número requerido de elementos para cada elemento de la array. Siga los pasos que se mencionan a continuación:
- Recorra la array y para cada elemento haga lo siguiente:
- recorrer los K elementos siguientes y los K anteriores y calcular la media de estos elementos.
- Imprime la respuesta para cada elemento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <iostream>
using namespace std;
// Function to calculate average
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
cout << ((leftSum + rightSum + arr[i])
* 1.0)
/ (2 * K + 1)
<< " ";
}
}
// Driver code
int 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 approach
import java.util.*;
public class GFG{
// Function to calculate average
static 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 code
public 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 average def 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 code arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] K = 3 N = len(arr) average(arr, N, K) # This code is contributed by Saurabh Jaiswal
C#
// C# code to implement the above approach
using System;
class GFG{
// Function to calculate average
static 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 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 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>
Producción
4.85714 4.57143 4.28571 4 5 6 5.71429 5.42857 5.14286
Complejidad de tiempo : O(N*K), ya que estamos usando bucles anidados para recorrer N*K tiempos.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.
Enfoque eficiente: para reducir la complejidad del tiempo, se puede usar el concepto de suma de prefijos donde la array de suma de prefijos (por ejemplo, preSum[]) se calcula como preSum[i] = arr[0] + . . . + arr[yo]. Y usando la array preSum[], la media se puede calcular fácilmente para cada elemento sin atravesar (2K + 1) elementos en cada iteración. Las condiciones para calcular la suma de los K elementos anteriores (leftSum) y los K elementos siguientes (rightSum) para cada uno de los elementos se indican a continuación:
Cálculo de la suma de K-elementos a la derecha:
- Si hay elementos K presentes en right:
rightSum = preSum[i + k] – preSum[i];- Si no hay elementos a la derecha:
rightSum = preSum[k – 1];- Si algunos elementos están a la derecha y algunos necesitan recorrido circular:
eleInRight = n – i – 1;
rightSum = presum[n – 1] – presum[i] + presum[k – eleInRight – 1];Cálculo de la suma de K-elementos a la izquierda:
- Si hay más de K elementos presentes en left:
leftSum = preSum[i – 1] – preSum[i – k – 1];- Si solo k elementos están presentes en left:
leftSum = preSum[i – 1];- si no hay elementos a la izquierda:
leftSum = preSum[n – 1] – preSum[n – 1 – k];- Si algunos elementos están a la izquierda y algunos necesitan recorrido circular:
eleInLeft = i
leftSum = presuSum[i – 1] + presuSum[n – 1] – presuSum[n – 1 – (k – eleInLeft)];
Siga los pasos que se mencionan a continuación para implementarlo:
- Iterar la array para crear la array de suma de prefijos.
- Para cada elemento, obtenga la suma izquierda y derecha como se muestra en la observación y calcule el promedio.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the average
void 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 code
int 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 approach
import java.util.*;
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];
}
}
System.out.print(((arr[i] + leftSum + rightSum)
* 1.0)
/ (2 * K + 1)
+ " ");
}
}
// Driver code
public 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 average
def 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 code
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
K = 3
N = len(arr)
average(arr, N, K)
# This code is contributed by Shubham Singh
C#
// C# code to implement the above approach
using 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>
Producción
4.85714 4.57143 4.28571 4 5 6 5.71429 5.42857 5.14286
Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar : O (N), ya que estamos usando espacio extra para presum.
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA