3
\$\begingroup\$

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;
    }
}



}
\$\endgroup\$
  • 2
    \$\begingroup\$ Sample sets of numbers and their corresponding solutions would be good to clarify the rules and the edge cases we need to handle \$\endgroup\$ – Stop ongoing harm to Monica Sep 20 '14 at 17:54
  • \$\begingroup\$ here you go: iarcs.org.in/inoi/contests/jan2005/Advanced-1-testdata.zip Please note that only the last 2 cases are exceeding the limit, the rest execute under time limit of 3 seconds. \$\endgroup\$ – pkj-m Sep 21 '14 at 7:49
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ +1 for the recommendation to ditch the sort. All you need is the averages from n pick 2 combinations. \$\endgroup\$ – Comintern Sep 21 '14 at 4:06
  • \$\begingroup\$ @Comintern That wouldn't work under the time limit of 3 seconds. My previous algorithm was exactly the same, looking for a pair for each element. That would give an O(n^3), and surely we don't want that. It actually got 30 points, against this algo which is an O(n^2) and got 80. \$\endgroup\$ – pkj-m Sep 21 '14 at 7:53
  • \$\begingroup\$ @Comintern I was actually arguing against home made sorting, not against sorting in general. Without sorting it could work with a HashSet containing all the desired sums, but that's probably a bit slower than the current algorithm, \$\endgroup\$ – maaartinus Sep 21 '14 at 11:19
  • \$\begingroup\$ @pkm What are you running it on? All 10 examples together using your algorithm take 1.1 seconds on my 4 years old computer. \$\endgroup\$ – maaartinus Sep 21 '14 at 11:22
  • \$\begingroup\$ @maaartinus Thanks for your replies. I solved the problem by following your suggestion of saving the difference in 1 variable instead of calculating it again and again. And I've no idea which oldie system is that website running it on. Even my laptop (5 year old i5) is able to run the program within a second or so. Thanks again. \$\endgroup\$ – pkj-m Sep 21 '14 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.