News Leaflets
A leading news portal.
0 46

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++

 ` `  `#include ` `using` `namespace` `std;` ` `  `vector<``int``> findIndices(``int` `N, ``int` `A[])` `{` ` `  `    ` `    ``vector<``int``> answer;` ` `  `    ` `    ``int` `sum = 0;` `    ``for` `(``int` `i = 0; i < N; i++) {` `        ``sum += A[i];` `    ``}` ` `  `    ` `    ` `    ` `    ``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);` `        ``}` `    ``}` ` `  `    ` `    ``return` `answer;` `}` ` `  `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] << ``" "``;` `    ``}` `}`

Time Complexity: O(N)
Auxiliary Space: O(N)

Read original article here

Denial of responsibility! News Leaflets is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.