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?

Answer 1

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;

Answer 2

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
}