sir how can i find gcd of n numbers in logarithm time as contraints are n<= 10^18.
Solving Linear Diophantine Equations
use euclidean gcd algorithm it find gcd of two number in log(n)
sir i m asking about n numbers i.e more than two numbers
If n numbers are there it going to take n*log(n).
take gcd of 1st and 2nd take gcd of 3rd with the result and so on…
sir is there any other optimization better than nlogn becoz constraints r too large nd i have to solve the problem in O(1),
no there is no algo from which you can do it in 0(1).
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.