Help in solving a randomized algorithm problem

Revision en2, by harsh-apcr, 2023-12-16 12:19:02

I was practicing randomised algorithm problems and I stumbled across this nice problem :

My approach to this problem is as follows : Let $$$g$$$ be the ghd of the input, then prob($$$g | a_i$$$) = 1/2 (where $$$a_i$$$ is random number from the input) thus with 1/2 probability $$$g$$$ is divisor of $$$a_i$$$, so divisors of $$$a_i$$$ can be good candidate for $$$g$$$

So my algorithm is repeat 20 times : take random number $$$a_i$$$ from the input array, compute its divisors iterate over its divisors list, and for each divisor $$$d$$$ of $$$a_i$$$, compute number of $$$a_j$$$ such that $$$d | a_j$$$, if it is $$$\geq \frac{n}{2}$$$ then $$$d$$$ is candidate $$$g$$$

Probability I don't get correct answer = probability in none of the 20 trails I get the correct $$$a_i$$$ = $$$1/2^{20}$$$ approx $$$10^{-6}$$$

Time complexity of the solution is : $$$O((n d + \sqrt{A})m)$$$ ,where $$$m$$$ is number of trails, $$$A = \textrm{max} a_i$$$, and $$$d$$$ is max number of divisors (which is typically very small and grows logarithmically)

Here is my submission link :

I am getting TLE, what can be the problem ?


  Rev. Lang. By When Δ Comment
en3 English harsh-apcr 2023-12-16 14:32:01 249
en2 English harsh-apcr 2023-12-16 12:19:02 5
en1 English harsh-apcr 2023-12-16 12:18:35 1198 Initial revision (published)