We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

actually for both of the steps 1 & 2 the complexity will be O(n log(b)).

Here n is the length of the array and b is the smaller integer of a pair(a,b) for which we calculate the GCD/LCM.

For simplicity we call it O(n log(n)) instead of O(n log(b)).

Explanation:
To calculate the GCD or LCM for the whole array we need to run a loop up to the length of the array which is n and inside that loop we need to calculate GCD/LCM which will take log(n). like below.

## Between Two Sets

You are viewing a single comment's thread. Return to all comments →

actually for both of the steps 1 & 2 the complexity will be

O(n log(b)).Here

nis the length of the array andbis the smaller integer of a pair(a,b) for which we calculate the GCD/LCM.For simplicity we call it O(n log(n)) instead of O(n log(b)).

Explanation: To calculate the GCD or LCM for the whole array we need to run a loop up to the length of the array which is

nand inside that loop we need to calculate GCD/LCM which will takelog(n). like below.so the complexity is O(n*log(n)). Same goes for LCM also.

Thanks!

I think previousGCD should be initialize with 1 not with array[0].

then your GCD will always be 1. Please do in pen and paper you will understand.

Silly mistake!! Got it