How do I improve the runtime complexity of this algorithm?

Question

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?

Provide some description about what the code is supposed to do and why do you want to make it worse by increasing time :) — sam
– sam, Commented Oct 2, 2015 at 22:15
You could turn one of the lists into a set, then iterate the other list and see whether the difference to 255 is in the set. — tobias_k
– tobias_k, Commented Oct 2, 2015 at 22:16

sve · Accepted Answer · 2015-10-05 16:07:01Z

4

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;

edited Oct 5, 2015 at 16:07

answered Oct 2, 2015 at 22:26

sve

4,3661 gold badge21 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

erickson Over a year ago

The product is 225, not 255.

erickson Over a year ago

And don't you want to divide by e instead of a?

Paul Boddington Over a year ago

Strictly speaking you'd have to deal with 15 separately. At the moment this would return true if 15 were in the array, whereas the original code required 15 to appear twice. The same goes for -15.

erickson Over a year ago

Still haven't dealt with a single occurrence of 15. Current solution is effectively if (225 % e == 0) return true;

erickson Over a year ago

Here's a test case: int[] a = { 15, 5, 45 } What does your method yield?

|

ig-melnyk · Accepted Answer · 2015-10-02 22:51:05Z

3

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
}

edited Oct 2, 2015 at 22:51

answered Oct 2, 2015 at 22:18

ig-melnyk

2,8992 gold badges28 silver badges35 bronze badges

1 Comment

aioobe Over a year ago

@tobias_k's approach should be O(n) assuming you have a uniform hash distribution.

JTY · Accepted Answer · 2015-10-02 22:53:27Z

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;

Lorenzo Belli · Accepted Answer · 2015-10-02 22:21:03Z

0

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

answered Oct 2, 2015 at 22:21

Lorenzo Belli

1,8494 gold badges26 silver badges47 bronze badges

Collectives™ on Stack Overflow

How do I improve the runtime complexity of this algorithm?

4 Answers 4

7 Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

7 Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related