I was asked this problem recently in an interview however, I failed to provide an optimal solution to it.

Problem: Given an array 𝐴 of 𝑛 numbers, the magic factor of 𝑖𝑡ℎ element is equal to the greatest prime factor 𝐺 where 𝐺 is the count of elements in the array strictly less than the element 𝐴[𝑖]. Now, the magical value of the array is the maximum possible magic factor for all the elements of the array.

Note: Magic factor for G = 0 is 0 and for G = 1 is 1.

Input: 1 2 3 4 5
Output: 3

Explanation: 𝐴 = [1,2,3,4,5]. Magic factors are [0,1,2,3,2]. Thus, the magical value of the array is max(0,1,2,3,2) = 3.

Constraints: 1 <= n < 10^5 , 1 <= A[i] <= 10^6

This is my logic below.

public static int magicValue(int[] arr) {
    Arrays.sort(arr);
    if(arr.length == 1)
      return 1;
    int G = 2, maxMagicValue = G;
    for(int i = 2; i < arr.length; i++) {
        int magicFactor = getMagicFactor(i);
        maxMagicValue = Math.max(magicFactor, maxMagicValue);
    }
    return maxMagicValue;
}

public static int getMagicFactor(int elem) {
    int magicFactor = 0;
    for(int i = 2; i <= elem; i++) {
        boolean isPrime = isPrime(i);
        if(isPrime && elem % i == 0)
                magicFactor = i;
    }
    return magicFactor;
}

public static boolean isPrime(int val) {
    boolean isPrime = true;
    for(int j = 2; j <= Math.sqrt(val); j++) {
        if(val % j == 0) {
            isPrime = false;
            break;
        }
    }
    return isPrime;
}

However it gave a TLE for the rest of the test cases.

Can someone please guide if I have misunderstood the question and if there is a more efficient way of solving this problem? Thanks.