Smallest Even Multiple - Leetcode Solution

The Smallest Even Multiple problem on LeetCode requires finding the smallest number that is divisible by both the given integers 'a' and 'b'. The answer is to be returned as a 32-bit signed integer.

One approach to solve this problem is by using the formula, LCM(a, b) = (a * b) / GCD(a, b), where LCM denotes the Least Common Multiple and GCD denotes the Greatest Common Divisor of a and b.

Algorithm:

1. Find the GCD of a and b using Euclid's algorithm.

   First, we need to find the greater number between a and b and assign it to a. Then we need to find the remainder of a/b. If the remainder is 0, then the GCD is b otherwise we need to assign b to a and the remainder to b and repeat the same step. Once the remainder is 0, the GCD is given by the value of b.

2. Calculate the LCM of a and b using the formula.

   To find the LCM, we can use the formula LCM(a, b) = (a * b) / GCD(a, b).

3. Return the LCM as a 32-bit signed integer

   Since the answer is to be returned as a 32-bit signed integer, we need to check if the LCM is within the range of -2^31 to 2^31 - 1. If it is outside the range, then we need to return the maximum or minimum value depending on whether it is negative or positive.

Code:

class Solution {
public:
    int lcm(int a, int b) {
        int g = gcd(a, b);
        if (g == 0) return 0;
        return (a / g) * b;
    }
    
    int gcd(int a, int b) {
        if (a > b) swap(a, b);
        while (b % a != 0) {
            int r = b % a;
            b = a;
            a = r;
        }
        return a;
    }
    
    int smallestEvenMultiple(int a, int b) {
        int l = lcm(a, b);
        if (l > INT_MAX || l < INT_MIN) return 0;
        if (l % 2 == 1) l = l + a * b / gcd(a, b);
        return l;
    }
};

Time Complexity:

The time complexity of the above solution is O(logn), where 'n' is the maximum of a and b. This is because the time taken by Euclid's algorithm to find the GCD between two numbers is proportional to the number of digits in the smaller number. Since the input integers 'a' and 'b' could be of maximum 32 bits, the algorithm will take at most log2(2^32)= 32 iterations to find the GCD.

1