CODEWITHSUNDEEP
javatime-complexity
Josh Susa
Josh Susa

Reputation: 173

How do I improve the runtime complexity of this algorithm?

public static boolean PP(int[] A){

    int n = A.length;

    for(int i = 0; i < (n-1); i++){             //finds one value in the array
        for(int j = (i+1); j < n; j++){         //compares all the other values with that one value
            if (A[i] * A[j] == 225){
                return true;
            }
        }
    }
    return false;               //returns false if it goes through the entire for loop without returning true
}

This code takes an array and tries to find two numbers that multiply to 225. If it finds two numbers then it returns true. Currently the running time is O(n^2) but I want to get a faster running time like O(nlogn) or O(n). So how do I decrease the running time of this?

Upvotes: 5

Views: 667

Answers (4)

sve
sve

Reputation: 4356

Here's a O(n) solution. You can use HashMap<Integer, Integer>. Insert (accumulatively) all elements from a with their count in HashMap<Integer, Integer> c and:

for (int e : a) {
     if (225 % e == 0) {
         int t = 225/e;
         if (c.containsKey(t)) {
             if (t == e) {
                 if c.get(t) >= 2)
                     return true;
             }
             else
                 return true;
         }
     }
}  
return false;

Upvotes: 4

JTY
JTY

Reputation: 1009

So you just simply want to find 2 values within an array that results to 225 when multiplied, and return true and instantly break the loop when found.

Iterate through A, and divide 225 by each value. Check if the hashset contains A[i], return true if it does. Else, store the division result in a hash set. Return false once you are done iterating through your array.

This should work because when A * B = 225, B = 225 / A.

This way, if we know A, we know what "B" will result true.

By storing A in a hashset, and you ever encounter a B where 225 / B is already in the hashset (which can be done in O(1)), then you know that you have your A * B = 225 pair.

By using a hashset, you can compare one value to the rest of the values in O(1), enabling you to compare all value in an array to every other value in O(n) time.

Set<Double> mySet = new HashSet<Double>();
for (int i = 0; i < N; i++) {
    double val = 225 / (double) A[i];
    if (mySet.contains(val)) {
        return true;
    }
    if (!mySet.contains((Double)A[i]) {
        mySet.add((Double)A[i]);
    }
}
return false;

Now note that I'm not putting all the values in in the hashset first and comparing everything. I'm comparing as I add to the hashset (This will still ensure that you have compared all values to each other once!) see below graphic:

// The below represents the above algo on an array with 10 elements.
// The values 0 ~ 9 are the index.
// The left row is my insert, and top row is my "compare." 
// Every intersection "[]" means that the value has been compared to each other.

   0  1  2  3  4  5  6  7  8  9
0     [] [] [] [] [] [] [] [] []
1        [] [] [] [] [] [] [] []
2           [] [] [] [] [] [] []
3              [] [] [] [] [] []
4                 [] [] [] [] []
5                    [] [] [] []
6                       [] [] []
7                          [] []
8                             []
9 

// You can see that every value actually compares to each other (except
// for itself. More on this below)

I have not added everything to the hashset first, and went with the "compare as we add" method because it has room for possibly unwanted error:

If by any chance you have a single instance of the value 15 within your array, you will compare 15 with itself this way, causing you to get 225 and returning true, but you may actually want a "unique" pair. (Now this is up to what kind of problem you are solving)

If by any chance your array was simply { 15 }, do you want to return true?

If your answer is true, switch the code around to add first, compare next:

Set<Double> mySet = new HashSet<Double>();
for (int i = 0; i < N; i++) {
    double val = 225 / (double) A[i];
    if (!mySet.contains((Double)A[i]) {
        mySet.add((Double)A[i]);
    }
    if (mySet.contains(val)) {
        return true;
    }
}
return false;

Upvotes: 2

ig-melnyk
ig-melnyk

Reputation: 2879

You can sort the array and then iterate over each element and find suitable element using binary search. Time complexity : O(N*logN) : 

public static boolean PP(int[] A){

    int N = A.length;

    Arrays.sort(A);
    for (int i = 0;i<N-2;i++){
        int a = A[i];
        if (a == 0)
            continue;
        int seek = 225 / a;
        int res = Arrays.binarySearch(A, i+1,N,seek);
        if(res>0 && A[res]*a==225)
            return true;
    }
    return false;               //returns false if it goes through the entire for loop without returning true
}

Upvotes: 3

Lorenzo Belli
Lorenzo Belli

Reputation: 1847

  1. create int B[] containing B[k]=255/A[k] - O(n) (discard the elements which are not perfect divisor)
  2. order A and B - O(n logn)
  3. search for common elements in the two ordered arrays - O(n)

Upvotes: 0

Related Questions