Explanation

545.Simplify a Fraction Using GCD

Easy
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.

Example 1:

Input: numerator = 12, denominator = 18

Output: [2,3]

Example 2:

Input: numerator = 7, denominator = 5

Output: [7,5]

+ 5 hidden test cases run on Submit.

Constraints:

  • ●1 ≤ numerator, denominator ≤ 1000000

numerator =

12

denominator =

18