How to make this linear time complexity to log time complexity?

Question

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

Answer 1

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.