n an array of N elements calculate its mean and count the number sub array of N-2 elements that have same mean

Question

The below code is getting TLE error i.e Time limit Exceeded Error. I am finding it difficult to solve it without using nested for loops.Can someone tell a faster logic or can improve this code.

#include <stdio.h>
    int mean(int arr[],int n,int b){             
        int m,s=0;
        for(int i=0;i<n;i++){
            s=arr[i]+s;
        }
        m=s/b;
        return m;
    }
    int main(void) {
        int t;
        scanf("%d",&t);
        while(t){
            int n;
            scanf("%d",&n);
            int arr[n];
            for(int i=0;i<n;i++)
                scanf("%d",&arr[i]);
            int x,c=0;
            int m=mean(arr,n,n);
            for(int i=0;i<n;i++){
                for(int j=i+1;j<n;j++){       
                    int a=arr[i];
                    int b=arr[j];
                    arr[i]=0;
                    arr[j]=0;
                    x=mean(arr,n,n-2);
                    if(x==m)
                        c++;
                    arr[i]=a;
                    arr[j]=b;
                }
            }
            printf("%d\n",c);
            t--;
        }
        return 0;
    }

Answer 1

The single-letter variable names make the code hard to read. Use more informative names to help readers understand what your code is doing.

Always assume input is erroneous or even hostile - never ignore the return value from scanf(). In fact, prefer not to use scanf() at all, unless you're going to give up completely on standard input when it fails.

Why does mean() return an int()? It's unlikely that the mean will be an exact integer.

You should improve the algorithm so that scales better. Instead of calling mean() on the whole n-2 subarray in the inner loop, keep a track of the running sum of those elements. That can be updated linearly. And there's no need to divide the sum each time around - just multiply up before you start, and then you just need to compare against the target sum.

Or even simpler - use your mathematical reasoning to realise that the problem is really a search for two elements whose mean is that of the entire array - i.e. we're looking for an a and b such that (a + b) * n / 2 == Σx. That is then just a variation on the well-known "2-sum" problem.