Dada una array arr[] de N enteros, la tarea es encontrar todos los índices en la array, de modo que para cada índice i la media aritmética de todos los elementos excepto arr[i] sea igual al valor del elemento en ese índice .
Ejemplos:
Entrada: N = 5, arr[] = {1, 2, 3, 4, 5}
Salida: {2}
Explicación: al eliminar el elemento de la array en el índice 2 (es decir, 3),
la media aritmética del resto de la array es igual a (1 + 2 + 4 + 5) / 4 = 3, que es igual al elemento en el índice 2.
Se puede ver que 2 es el único índice de este tipo.Entrada: N = 6, arr[] = {5, 5, 5, 5, 5, 5}
Salida: {0, 1, 2, 3, 4, 5}
Enfoque: El problema se puede resolver con la siguiente idea:
Calcule la suma total de la array y para cada elemento (arr[i]) verifique si el promedio de todos los demás elementos es el mismo que arr[i].
Siga los pasos para resolver el problema:
- Encuentre la suma de todos los elementos de la array y guárdela en una variable, digamos sum.
- Atraviesa la array y,
- En cada iteración, encuentre la suma de la array sin el elemento actual restando el valor del elemento actual de la suma. decir, current_sum
- Encuentre la media de current_sum , dividiéndola por N-1
- Si la media es igual al valor en el índice actual, empuje el índice en el vector de respuesta , de lo contrario, continúe.
- Devuelve el vector de respuesta .
El siguiente es el código basado en el enfoque anterior:
C++
// C++ code for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find indices such that
// elements at those indices equals to the
// mean of the array except those indices
vector<int> findIndices(int N, int A[])
{
// Vector to store answer (i.e. indices)
vector<int> answer;
// Calculation of sum of all elements
int sum = 0;
for (int i = 0; i < N; i++) {
sum += A[i];
}
// For each element checking if its
// value is equal to the mean of the
// array except the current element
for (int i = 0; i < N; i++) {
int curr_sum = sum - A[i];
if (curr_sum % (N - 1) == 0
&& curr_sum / (N - 1) == A[i]) {
answer.push_back(i);
}
}
// returning answer
return answer;
}
// Driver Code
int main()
{
int N = 5;
int A[] = { 5, 5, 5, 5, 5 };
vector<int> ans = findIndices(N, A);
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
}
Java
// Java code for above approach
import java.util.*;
class GFG {
// Function to find indices such that
// elements at those indices equals to the
// mean of the array except those indices
static Vector<Integer> findIndices(int N, int[] A)
{
// Vector to store answer (i.e. indices)
Vector<Integer> answer = new Vector<Integer>();
// Calculation of sum of all elements
int sum = 0;
for (int i = 0; i < N; i++) {
sum += A[i];
}
// For each element checking if its
// value is equal to the mean of the
// array except the current element
for (int i = 0; i < N; i++) {
int curr_sum = sum - A[i];
if (curr_sum % (N - 1) == 0
&& curr_sum / (N - 1) == A[i]) {
answer.add(i);
}
}
// returning answer
return answer;
}
// Driver Code
public static void main (String[] args) {
int N = 5;
int A[] = { 5, 5, 5, 5, 5 };
Vector<Integer> ans = findIndices(N, A);
for (int i = 0; i < ans.size(); i++) {
System.out.print(ans.get(i) + " ");
}
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python code for above approach # Function to find indices such that # elements at those indices equals to the # mean of the array except those indices def findIndices(N, A): # Vector to store answer (i.e. indices) answer = [] # Calculation of sum of all elements sum = 0 for i in range(0, N): sum += A[i] # For each element checking if its # value is equal to the mean of the # array except the current element for i in range(0, N): curr_sum = sum - A[i] if (curr_sum % (N - 1) == 0 and curr_sum // (N - 1) == A[i]): answer.append(i) # returning answer return answer # Driver Code N = 5 A = [5, 5, 5, 5, 5] ans = findIndices(N, A) print(*ans) # This code is contributed by Samim Hossain Mondal.
C#
// C# code for above approach
using System;
using System.Collections;
class GFG {
// Function to find indices such that
// elements at those indices equals to the
// mean of the array except those indices
static ArrayList findIndices(int N, int[] A)
{
// Vector to store answer (i.e. indices)
ArrayList answer = new ArrayList();
// Calculation of sum of all elements
int sum = 0;
for (int i = 0; i < N; i++) {
sum += A[i];
}
// For each element checking if its
// value is equal to the mean of the
// array except the current element
for (int i = 0; i < N; i++) {
int curr_sum = sum - A[i];
if (curr_sum % (N - 1) == 0
&& curr_sum / (N - 1) == A[i]) {
answer.Add(i);
}
}
// returning answer
return answer;
}
// Driver Code
public static void Main()
{
int N = 5;
int[] A = { 5, 5, 5, 5, 5 };
ArrayList ans = findIndices(N, A);
for (int i = 0; i < ans.Count; i++) {
Console.Write(ans[i] + " ");
}
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
// JavaScript code for the above approach
// Function to find indices such that
// elements at those indices equals to the
// mean of the array except those indices
function findIndices(N, A) {
// Vector to store answer (i.e. indices)
let answer = [];
// Calculation of sum of all elements
let sum = 0;
for (let i = 0; i < N; i++) {
sum += A[i];
}
// For each element checking if its
// value is equal to the mean of the
// array except the current element
for (let i = 0; i < N; i++) {
let curr_sum = sum - A[i];
if (curr_sum % (N - 1) == 0
&& curr_sum / (N - 1) == A[i]) {
answer.push(i);
}
}
// returning answer
return answer;
}
// Driver Code
let N = 5;
let A = [5, 5, 5, 5, 5];
let ans = findIndices(N, A);
for (let i = 0; i < ans.length; i++) {
document.write(ans[i] + " ")
}
// This code is contributed by Potta Lokesh
Producción
0 1 2 3 4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kamabokogonpachiro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA