Find the simplest rational number between two given rational numbers
Data Structures & Algorithms practice on Codemia
Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.
When tasked with finding the simplest rational number that exists between two given rational numbers, you're essentially looking for the smallest numerator and denominator such that this number still sits between the bounds provided. This exercise involves understanding the properties of rational numbers and employing mathematical techniques like mediants to solve the problem.
Understanding Rational Numbers
A rational number is defined as a number that can be expressed as the quotient of two integers, where the denominator is not zero. If a
and b
are integers, then the rational number can be represented as .
To solve our problem, we must focus on identifying a way to determine a rational number—one whose simplest form fits between two others.
Mediants
A mediant offers a practical approach to finding a rational number between two others. The mediant of two fractions $\frac\{a\}\{b\}$ and $\frac\{c\}\{d\}$ is given by:
The mediant fraction lies strictly between the original two fractions, assuming . This is handy because it guarantees that the new fraction is sandwiched precisely between the two. However, note that this is not yet the simplest nor the only rational number between them.
Simplifying the Rational Number
Simplest Form
A fraction is in its simplest form if there's no common divisor for the numerator and the denominator other than one. While the mediant gives a new fraction in between our bounds, it must be reduced if necessary. Simplifying involves finding the greatest common divisor (GCD) of the numerator and denominator and dividing both by this value.
Algorithm for GCD
To simplify fractions using the Euclidean algorithm for GCD: • Given two numbers, divide the larger by the smaller and take the remainder. • Replace the larger number with the smaller and the smaller number with the remainder. • Repeat this process until the remainder is zero; the last non-zero remainder is the GCD.
Example
Suppose you have two fractions $\frac\{2\}\{5\}$ and $\frac\{3\}\{4\}$, and need to find the simplest rational number between them.
- Verify Inequality: by cross-multiplying: .
- Calculate Mediants:
Related reading
- Find the single wrong element in matrix product?
- find the smallest containing convex polygon with a given number of points
- Find the smallest positive integer that does not occur in a given sequence
- Find the smallest regular number that is not less than N
- Find the sum of all numbers between 1 and N divisible by either x or y
- Find the sum of least common multiples of all subsets of a given set
- Find the sum of maximum difference of all possible subarrays
- Find two missing numbers

DSA Fundamentals
Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.
View the courseTrack what you have practised
A free account saves your progress, solutions and study plan across every problem on Codemia.
Data Structures & Algorithms practice on Codemia
Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.