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