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

• janos: Sample sets of numbers and their corresponding solutions would be good to clarify the rules and the edge cases we need to handle
• pkj-m: 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.

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.

• Comintern: +1 for the recommendation to ditch the sort. All you need is the averages from n pick 2 combinations.
• pkj-m: @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.
• maaartinus: @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,
• maaartinus: @pkm What are you running it on? All 10 examples together using your algorithm take 1.1 seconds on my 4 years old computer.
• pkj-m: @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.