Determining average of integers using quicksort

Question

I was attempting an online problem given on a programming website which asked us to tell us the number of integers in a given list which can be obtained as an average of any two other integers in that list, where one of them can be equal to the average (so the other is obviously equal too).

The server tells me that my program exceeded the time limit for the last two test cases. So I would like to make my algorithm faster.

I've tried both the inbuilt Java sort function as well as my own implementation of quicksort. I tried the test data on my own computer and it gives the output within a second.

My program basically sorts the array first, and then searches for a pair in linear time.

import java.util.*;

public class Average {

public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        int[] a = new int[n];

        for (int i = 0; i < n; i++){
            a[i] = in.nextInt();

        }

        quickSort(a, 0, n - 1);

         int z = 0;

         for (int k = 0; k < n; k++){
             int s = 2 * a[k];
             int l = 0;
             int r = n-1;
             while (l < r){
                if (a[l] + a[r] == s){

                        z++;
                        break;

                }
                if (a[l] + a[r] < s){
                    l++;
                }else{
                    r--;
                }
             }

         }

         System.out.println(z); 
         System.exit(0);
}


//QUICKSORT FUNCTION

private static void swap(int[] a, int i, int j) {
    // TODO Auto-generated method stub
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

public static void quickSort(int[] a, int p, int r)
{
    if(p<r)
    {
        int q=partition(a,p,r);
        quickSort(a,p,q);
        quickSort(a,q+1,r);
    }
}

private static int partition(int[] a, int p, int r) {

    int x = a[p];
    int i = p-1 ;
    int j = r+1 ;

    while (true) {
        i++;
        while ( i< r && a[i] < x){
            i++;}
        j--;
        while (j>p && a[j] > x){
            j--;}

        if (i < j)
            swap(a, i, j);
        else
            return j;
    }
}



}

Answer 1

Just a few comments:

You can't really hope that your quicksort will be faster than what Java provides. I'm not saying, it can't be done, but it'd take an excellent programmer a few days at best.

So let's forget this part... and now to your algorithm. After some reformatting, I might understand it:

int result = 0;

for (int k = 0; k < n; k++) {
    int desired = 2 * a[k];
    int l = 0;
    int r = n-1;
    while (l < r) {
        int diff = a[l] + a[r] - desired;
        // made symmetric
        if (diff < 0) {
            l++;
        } else if (diff > 0) {
            r--;
        } else {
            result++;
            break;
        }
    }
}

You really seem to be doing what you stated. The total time is quadratic, so let's forget the sorting once again.

Some better variable naming would surely do no harm.

I'll come back when I get an idea concerning the speed.