How to improve the 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 are multiplied by 225. If it finds two numbers, 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 can I shorten the execution time of this?

Answer 1

Here is a O(n)solution. You can use HashMap<Integer, Integer>. Insert (cumulatively) all elements from awith their counter in HashMap<Integer, Integer> cand:

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;

Answer 2

, , . : 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
}

Answer 3

, 2 , 225, true .

A 225 . , hashset A [i], true, . Else, -. false, .

, A * B = 225, B = 225 / A.

, , , "B" .

A hashset, - B, 225/B hashset ( O (1)), , A * B = 225 .

hashset, O (1), O (n) .

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;

, . , hashset ( , !) . :

// 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)

", ", :

15 , , 225 true, "" . ( , )

If your array were simple { 15 }, do you want to return true?

If your answer is correct, first switch the code to add, compare the following:

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;

Answer 4

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