Help in solving a randomized algorithm problem
Difference between en2 and en3, changed 249 character(s)
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 ?

UPDATE : I did some optimizations, and passed the 3rd test-case now I am stuck at 4th↵
These two test cases are very similar I don't know why there is this problem↵

updated submission :


  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)