GCD of an array

help
,
1

This question was asked in InterviewBit Academy Enterance Test on 16 Feb.

Problem Description :
Given an integer array A of size N. You can delete at most B elements from the array such that the GCD(Greatest commmon divisor) of the remaining array is maximum. Find the maximum GCD of the remaining array.

Constraints :
1 \leq N \leq 10^{4}
1 \leq A[i] \leq 5 \times 10^{4}
0 \leq B < N

Please suggest the approach of this problem.

5 Likes
2

Maintain a count array to store the count of divisors of every element in
A, iterate and find the greatest divisor with count >= (N - B),
time complexity O(N*sqrt(max(A[i])))works for this problem.
else use a linear sieve (SPF) to prime-factorize and recurse on them
to get O(max(#div(A[i]))) factor instead of sqrt(max(A[i])) ,
if N is too large use Pollard’s rho, to overcome space constraints.

1 Like