Link to the problem:CSES - Common Divisors My approach: I came up with an O(n\sqrt{x}) algorithm. I go through each of the numbers and then find their factors using the O(\sqrt{x}) algorithm, and then update the frequency array of the possible factors (with size being equal to the maximum possible number), and then once I have built the frequency array, I go in the reverse order from the largest possible number to 1, and the moment I find that for a factor i, frequency[i] > 1, I stop the traversal. And finally I report the answer as i. My code:
My question: Even though this approach gets an AC, but its still quite slow. Can we do better? If yes (most probably), how can we do it? Are there any other concepts that are needed over here?
Sieve Of Eratosthenes method can be used to solve this problem effieciently. Even codechef DSA learning series also covered this topic in youtube. Here is link from geeksforgeeks for quick reference. Find pair with maximum GCD in an array - GeeksforGeeks