# [SOLVED] How to make this linear time complexity to log time complexity?

## Issue

I was practising for a coding challenge and I got stuck up with this problem.

A and his friend bought a number each from the integer shop, A has number N and his friend has number M. A wants that both their numbers should be co-primes. To achieve this, A divides both the numbers by the largest number which can divide both the numbers. A wants to know the sum of numbers after doing this operation, help him find that sum.

Input

``````Input:
N = 6, M = 5
Output:
11
Explanation:
The largest number that can divide both
5 and 6 is 1.
After dividing, 5+6 = 11.
``````

I have tried this code

``````long sum(long N, long M){
long divider = 1;
long min = Math.min(N,M);
for(long i=2; i<=min; i++)
if(N%i==0 && M%i==0)
divider=i;
return (N/divider) + (M/divider);
}
``````

But the expected run-time complexity is O(log(n)).
But my code gives O(n).

I’m not able to find any method to make it logarithmic. Please any help me.
😀😀

## Solution

You should use any efficient algorithm to find GCD – Greatest Common Divisor. E.g. you can try Euclidean algorithm with `O(log(min(N, M))` time complexity.

``````public static long sum(long N, long M) {
long gcd = gcdEuclideanAlgorithm(N, M);
return (N / gcd) + (M / gcd);
}

private static long gcdEuclideanAlgorithm(long a, long b) {
return b == 0 ? a : gcdEuclideanAlgorithm(b, a % b);
}
``````

More algorithms you can find here.