## 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.

Answered By – oleg.cherednik

Answer Checked By – Jay B. (BugsFixing Admin)