Given two positive integers n1 and n2, return their least common multiple (LCM), the smallest positive integer divisible by both numbers.
Example 1
Input: n1 = 14, n2 = 8
Output: 56
Explanation: 56 is the smallest positive number divisible by both 14 and 8.
Example 2
Input: n1 = 9, n2 = 10
Output: 90
Explanation: 90 is the smallest positive number divisible by both 9 and 10.
Brute Force Approach
The LCM must be a multiple of both inputs. Considering the multiples of the larger number automatically satisfies one of these requirements, leaving only divisibility by the smaller number to check.
These multiples appear in increasing order. Therefore, the first one divisible by the smaller number must be the smallest common multiple.
Algorithm
Identify the larger and smaller inputs.
Examine the positive multiples of the larger input in increasing order.
Check whether each multiple is divisible by the smaller input.
Return the first multiple that passes this check.
Dry Run
lcm of two numbers - Brute
Solution
#include<bits/stdc++.h>using namespace std;class Solution {public: // Returns the LCM of two positive integers. long long LCM(int n1, int n2) { long long larger = max(n1, n2); int smaller = min(n1, n2); // Use a wider type because the LCM may exceed an int. long long candidate = larger; // Every candidate is already divisible by the larger input. while (candidate % smaller != 0) { // Move to the next multiple of the larger input. candidate += larger; } // The first matching multiple is the smallest common multiple. return candidate; }};// Driver codeint main() { int n1 = 14; int n2 = 8; // Create an instance of class Solution. Solution sol; cout << sol.LCM(n1, n2) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(min(N1, N2)) in the worst case. The product N1 × N2 is always a common multiple, so at most min(N1, N2) multiples of the larger input need to be checked.
Space Complexity: O(1) auxiliary space because only a fixed number of variables are stored.
Optimal Approach
Multiplying the two inputs always produces a common multiple, but shared factors can make that product larger than necessary. Dividing by their greatest common divisor (GCD) removes the extra shared factor and gives the smallest common multiple.
This produces the relationship:
LCM(n1, n2) = (n1 / GCD(n1, n2)) × n2
Algorithm
Find the GCD by repeatedly replacing the current pair with its second number and the remainder of dividing the first by the second.
Stop when the second number becomes zero; the remaining number is the GCD.
Divide one original input by the GCD, then multiply by the other original input.
Return the resulting LCM.
Dry Run
lcm of two numbers - optimal
Solution
#include<bits/stdc++.h>using namespace std;class Solution {private: // Finds the GCD manually using repeated remainders. int gcd(int a, int b) { while (b != 0) { // Replacing the pair with (b, remainder) preserves its GCD. int remainder = a % b; a = b; b = remainder; } // When the second value is zero, the first value is the GCD. return a; }public: // Returns the LCM of two positive integers. long long LCM(int n1, int n2) { // Use the manually implemented helper to find the shared divisor. int commonGcd = gcd(n1, n2); // Divide first, then perform multiplication using 64-bit arithmetic. return 1LL * (n1 / commonGcd) * n2; }};// Driver codeint main() { int n1 = 14; int n2 = 8; // Create an instance of class Solution. Solution sol; cout << sol.LCM(n1, n2) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(log(min(N1, N2))), because the remainder-based GCD calculation takes logarithmic time. Calculating the LCM from the GCD takes constant time.
Space Complexity: O(1) auxiliary space because the GCD helper is iterative and uses only a fixed number of variables.
Interview follow-up Questions
The GCD divides each input exactly, so (n1 / GCD) × n2 produces the same result as (n1 × n2) / GCD. Dividing first keeps the intermediate value smaller and reduces overflow risk. The final result must still fit the chosen number type. The JavaScript implementations assume that both inputs and the LCM are safe integers, no greater than Number.MAX_SAFE_INTEGER.
Be the first to add a comment.