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.