LCM and GCD

Problem

Given two integers a and b, write a function lcmAndGcd() to compute their LCM and GCD. The function takes two integers b and b as input and returns a list containing their LCM and GCD.

Examples:

Example 1:

Input: a = 5 , b = 10
Output: 10 5
Explanation: LCM of 5 and 10 is 10, while thier GCD is 5.

Example 2:

Input: a = 14 , b = 8
Output: 56 2
Explanation: LCM of 14 and 8 is 56, while thier GCD is 2.

• Expected Time Complexity: $O(log(min(a, b))$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1 <= a, b <=10^9$

Solution

Python

def lcmAndGcd(self, A , B):
    def g(a,b):
        if (b == 0):
                return a
        return g(b, a%b)
        
    gcd = g(A, B)
    lcm = A*B//gcd
    return lcm, gcd

Java

static Long[] lcmAndGcd(Long A , Long B) {
    long gcd = calculateGCD(A, B);
    long lcm = (A * B) / gcd;
    return new Long[] {lcm, gcd};
}

static long calculateGCD(long a, long b) {
    if (b == 0) {
        return a;
    }
    return calculateGCD(b, a % b);
}

C++

public:
vector<long long> lcmAndGcd(long long A , long long B) {
    long long gcd_val = gcd(A, B);
    long long lcm_val = (A / gcd_val) * B; 
    return {lcm_val, gcd_val};
}

private:
long long gcd(long long a, long long b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

C

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long lcm(long long a, long long b) {
    return (a / gcd(a, b)) * b;
}

void lcmAndGcd(long long A, long long B, long long *lcm_result, long long *gcd_result) {
    *gcd_result = gcd(A, B);
    *lcm_result = lcm(A, B);
}

• Time Complexity: $O(log(min(a, b))$
• Auxiliary Space: $O(1)$