O(nlgn) complexity for unlisted array comparison?

Question

Consider two sum,X=x1+x2+...+xn, and Y=y1+y2+...+ym. Give an algorithm that finds indices i and j such that swapping xi with yj makes the two sums equal,that is , X-xi+yj = Y-yj+xi ,if they exist.

Hi guys! so up there you can see the description. So firstly i am getting two unsorted arrays. then i sort them. then I have to subtract them from each other in order to find the difference between them then in two for loops i compare array's elements difference.

so here is my code

Timport java.util.ArrayList;


public class algorithm {
int j;
int i;
int key;

public algorithm() {
    super();
    // TODO Auto-generated constructor stub
}

public ArrayList<Integer> sortingFunction(ArrayList<Integer> array){
    for(j=1;j<array.size();j++){
            key = array.get(j);
            i = j - 1;          
        while (i>=0 && array.get(i)>key){
            array.set(i+1, array.get(i));
            i = i - 1;  
        }
        array.set(i+1, key);
    }
    return array;
}


public int calculationFunction(ArrayList<Integer> array){
    int sum = 0;
    for(int x = 0; x<array.size(); x++){
        sum += array.get(x);
    }
        return sum;
}

public void writingFunction(ArrayList<Integer> array){
    for(int x = 0; x<array.size(); x++){
        System.out.print(array.get(x)+"  ");
    }
    System.out.println();
}

public void twoSumsEqualAlgorithm (int x, int y, ArrayList<Integer> array1, ArrayList<Integer> array2 ){
    int x_copy = x;
    int y_copy = y;
    //System.out.println(x);
    //System.out.println(y);
    for(int i = 0; i<array2.size(); i++){
        x_copy = x + (array2.get(i) * 2);
        //System.out.print("x;"+ x_copy);
        //System.out.println("  y;"+ y);
        if(x_copy >= y){
            for(int j = 0; j<array1.size(); j++){
                y_copy = y + (array1.get(j) * 2);
                if(x_copy == y_copy){
                    System.out.print("we have found the true values; ");
                    System.out.print("'"+array1.get(j)+"'"+" from myArray1("+j+ ") and ");
                    System.out.println("'"+array2.get(i)+"'"+" from myArray2("+i+")");
                    //return;
                }
                else if(x_copy < y_copy){
                    //System.out.println("x is lower than y");
                    break;
                }
            }
        }


    }

}

private void exit(int k) {
    // TODO Auto-generated method stub

}


}

and this is the test part

import java.util.ArrayList;


public class test {

/**
 * @param args
 */
public static void main(String[] args) {
     ArrayList<Integer> myArr1 = new ArrayList<Integer>();
     ArrayList<Integer> myArr2 = new ArrayList<Integer>();
     algorithm alg = new algorithm();

     myArr1.add(8);
     myArr1.add(4);
     myArr1.add(2);
     myArr1.add(15);
     myArr1.add(10);
     myArr1.add(16);
     myArr1.add(1);
     myArr1.add(11);


     myArr2.add(5);
     myArr2.add(3);
     myArr2.add(7);
     myArr2.add(6);
     myArr2.add(19);
     myArr2.add(2);
     myArr2.add(12);
     myArr2.add(1);
     myArr2.add(0);




     myArr1 = alg.sortingFunction(myArr1);
     myArr2 = alg.sortingFunction(myArr2);

     System.out.print("myArray1; ");
     alg.writingFunction(myArr1);
     System.out.print("myArray2; ");
     alg.writingFunction(myArr2);

     System.out.print("sum of myarray1; ");
     System.out.println(alg.calculationFunction(myArr1));
     System.out.print("sum of myarray2; ");
     System.out.println(alg.calculationFunction(myArr2));

     alg.twoSumsEqualAlgorithm(alg.calculationFunction(myArr1), alg.calculationFunction(myArr2), myArr1, myArr2);



}




}

so i think when i calculate the complexity of my algorithm it is O(n^2). I read some posts and it says i can do the same job with O(nlgn) complexity.

comparing two array list can done in a way which will lead to a a lower big-O But with >sorting.

You can sort each arraylist using mergesort or quicksort O(nlg(n)) then compare the two >sorted lists in O(n). the result is O(nlgn).

But another algorithm (without sorting) would iterate over each element in one array (n). And >then checks whether the element is another array (n) (and marks it to handle duplicates >properly). This latter algorithm is O(n^2).

Comparing two sorted int arrays

so i just couldn't a way to implement. Any ideas?

Answer 1

What you want to do is NOT a comparison of two arrays. It's similar in design but a completely different task that I would solve like this:

1) Mergesort or quicksort both collections. This is O(nlgn) when well designed.

2) Add up the numbers in collection x and collection y, and calculate X-Y as the difference D. O(n).

3) (Assuming D is negative) Do a scan of x from smallest to largest, and a scan of y from largest to smallest. For each element in the scan of x, check each element in the scan of y until swapping x and y would make D go PAST zero. If this happens, advance x and continue checking elements in the scan of y (e.g. don't reset the scan of y each time you advance the scan of x).

If you get D to exactly hit zero, then you've found your swap. This is at worst O(n), because you read x's elements exactly once, and read y's elements at most x.length+y.length times.

4) (assuming D is positive) Do similar logic to the above but scan x from largest to smallest and y from smallest to largest.

Answer 2

So you need to solve xi-yj == (X-Y)/2

Sort the y array and loop over the x array. For each x_i do a binary search in the y array for (X-Y)/2-xi. If you find something stop, otherwise continue. The complexity for the sort is O(n log n). The complexity for each lookup in O(log n) and you need at most n lookups --> total complexity is O(n log n)