Simplify a Fraction Using GCD
Solve this ProblemEasy10 min
Topics
BasicsFunctionsMath
Companies
TCSInfosysWipro
Given a fraction as
numerator and denominator, return it in lowest terms as [newNumerator, newDenominator].
A fraction is in lowest terms when the top and bottom share no factor above 1. Dividing both by their greatest common divisorGreatest Common Divisor (GCD)The largest whole number that divides two numbers exactly, e.g. 6 for 12 and 18. gets there in one step. Putting the GCD calculation in its own helper keeps simplifyFraction to two lines, and lets the helper use Euclid's algorithmEuclid's AlgorithmFinds the GCD by repeatedly replacing (a, b) with (b, a % b) until b is 0., which is dramatically faster than trying every candidate.
Test Case 1:
Input:numerator = 12, denominator = 18
Output:[2, 3]
Explanation:6 is the largest number dividing both, and 12/6 = 2, 18/6 = 3.
Test Case 2:
Input:numerator = 7, denominator = 5
Output:[7, 5]
Explanation:They share no common factor above 1, so the fraction is already in lowest terms.
Constraints
- ◆
1 ≤ numerator, denominator ≤ 1000000
Try the Dry Run
Approach & Solutions
Try Common Divisors from the TopBrute
Start at the smaller of the two numbers and count down. The first d that divides both the numerator and the denominator is their greatest common divisor. Divide both by it. In the worst case (no common factor) the loop runs all the way down to 1.
Time
O(min(a, b))Space
O(1)Java
class Solution {
public int[] simplifyFraction(int numerator, int denominator) {
int common = 1;
for (int d = Math.min(numerator, denominator); d >= 1; d--) {
if (numerator % d == 0 && denominator % d == 0) {
common = d;
break;
}
}
return new int[] {numerator / common, denominator / common};
}
}Euclid's gcd() HelperOptimal
Write a gcd(a, b) helper using Euclid's rule: the gcd of a and b equals the gcd of b and a % b. Keep replacing (a, b) with (b, a % b) until b becomes 0; a is then the gcd. The numbers shrink very fast, so even a million needs only a handful of steps. Divide both parts of the fraction by the result.
Time
O(log min(a, b))Space
O(1)Java
class Solution {
int gcd(int a, int b) {
while (b != 0) {
int rest = a % b;
a = b;
b = rest;
}
return a;
}
public int[] simplifyFraction(int numerator, int denominator) {
int common = gcd(numerator, denominator);
return new int[] {numerator / common, denominator / common};
}
}