Given an array arr[] of N integers, the task is to find all indices in the array, such that for each index i the arithmetic mean of all elements except arr[i] is equal to the value of the element at that index.
Examples :
Input: N = 5, arr[] = {1, 2, 3, 4, 5}
Output : {2}
Explanation : Upon removing array element at index 2 (i.e. 3),
arithmetic mean of rest of the array equals (1 + 2 + 4 + 5) / 4 = 3, which is equal to the element at index 2.
It can be seen that 2 is the only such index.Input : N = 6, arr[] = {5, 5, 5, 5, 5, 5}
Output : {0, 1, 2, 3, 4, 5}
Approach: The problem can be solved by the following idea:
Calculate the total sum of the array and for each element (arr[i]) check if the average of all the other elements is same as arr[i].
Follow the steps to solve the problem:
- Find sum of all elements of the array and store in a variable say sum.
- Traverse the array and,
- At each iteration, find the sum of the array without current element by subtracting current element value from the sum. say, current_sum
- Find the mean of current_sum, by dividing it with N-1
- If mean is equal to the value at current index, push the index in answer vector, else continue.
- Return the answer vector.
Following is the code based on above approach :
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 indicesvector<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 Codeint 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 approachimport 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 indicesdef 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 CodeN = 5A = [5, 5, 5, 5, 5]ans = findIndices(N, A)print(*ans)# This code is contributed by Samim Hossain Mondal. |
C#
// C# code for above approachusing 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 |
Output
0 1 2 3 4
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
