Count of triplets that can be removed without changing Mean of given Array

Given an integer array arr[], the task is to find the number of triplets at distinct indices that can be removed from the array such that the mean remains the same as before.

Example:

Input: arr[]= { 8, 7, 4, 6, 3, 0, 7}
Output: 3
Explanation:
The mean of the array is (8+7+4+6+2+1+7)/7 = 5
On removal of triplets {6,4,0},{3,0,7} and {7,3,0} the mean of the arrays remain the same so the answer is 3.

Input: arr[] = {5,5,5,5}
Output: 4

Approach:

Mean of the array m = sum of the array/size of the array

m = sum/n => m* n = sum ----> 1

let the pair to be removed be (x,y,z) and the mean should be same after removal of two elements.

m = (sum-x-y-z)/(n-3)

m = (sum-x-y-z)/(n-3)

m*n - 3* m = sum-(x+y+z) ---> 2

Substituting eq 1 in eq 2

sum - 3* (sum/n) = sum -(x+y+z)

=> 3* (sum/n) = (x+y+z)

It can be concluded that the pair sum should be equal to the 3 times mean of the previous array before removal. So we need to find number of triplets that has sum 3* (sum/n) in the original array at different indices.

Follow the steps below to solve the problem:

Initialize a variable sum = 0 and find the sum of the array arr[] by iterating through the array arr in the range (0,n).
Now find the mean which is sum/n of the array and store it in the mean variable.
From the above illustration triplet_sum = 3* (sum/n).
Using count_triplets_helper() function find the number of triplets that sum to triplet_sum.
Store the result in the variable ans and return the ans which is the number of triplets that can be removed and still the mean remains the same.

Below is the implementation of the above approach.

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;

// Function to count the number of triplets 
int count_triplets_helper(int arr[], int n, int sum)
{
    int cnt = 0;
    unordered_map<int, int> m;
    for (int i = 0; i < n - 1; i++)
    {
        // check if  sum-arr[i]-arr[j] is present in the map
        for (int j = i + 1; j < n; j++)
        {
            int k = sum - (arr[i] + arr[j]);
            if (m.find(k) != m.end())
                cnt += m[k];
        }
// Store the occurences
        m[arr[i]]++;
    }
    return cnt;
}

// Function to count the number of triplets in the
// in the array on whose removal mean remains same
int count_triplets(int arr[], int n)
{
    int sum = 0;
    // Calculate the sum of the array
    for (int i = 0; i < n; i++)
    {
        sum = sum + arr[i];
    }
    // Store the mean
    int mean = sum / n;
    int triplet_sum = 3 * mean;
    // If triplet_sum  is not divisible by n return 0
    if ((3 * sum) % n != 0)
        return 0;
 
    int ans = count_triplets_helper(arr, n, triplet_sum);

    return ans;
}

// Driver Code
int main()
{
      // Initializing array of arr
    int arr[] = {8, 7, 4, 6, 3, 0, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    // Calling the function
    int res = count_triplets(arr, n);
    cout << res<<endl;
    return 0;
}

Output

Time Complexity : O(n*n) where n is the size of the array
Space Complexity : O(n)