MEX Dividend

Let’s approach the problem like the sieve of Eratosthenes. For each integer, $A_i$ we will find the smallest integer divisible by $A_i$ which is not present in the array. The time complexity of this approach will be the sum of number of divisors for all $A_i$, which is not enough for the given constraints.

Optimization: Let’s process the array in nondecreasing order, for each $A_i$​ if we visited $A_i$ for a smaller number $A_j$($A_j$ is a divisor of $A_i$), ​ we don’t need to process this $A_i$ as while processing $A_j$ we would have countered the result for $A_i$ too. The time complexity of this approach will be the sum of number of prime divisors for all $A_i$​, which should be fast enough.

Time Complexity: $O(n*log(log(A_i)))$

Space Complexity: $O(n)$