rational numbers
number theory
mathematics
fractions
math education

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.

Practice algorithms

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 ab\frac{a}{b}.

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:

a+cb+d\frac{a+c}{b+d}

The mediant fraction lies strictly between the original two fractions, assuming ab<cd\frac{a}{b} < \frac{c}{d}. 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\&#123;2\&#125;\&#123;5\&#125;$ and $\frac\&#123;3\&#125;\&#123;4\&#125;$, and need to find the simplest rational number between them.

  1. Verify Inequality: 25<34\frac{2}{5} < \frac{3}{4} by cross-multiplying: 2×4=8,3×5=15;8<152 \times 4 = 8, \,\,3 \times 5 = 15; \,\,8 < 15.
  2. Calculate Mediants:

Related reading
Course
Intermediate
27 lessons
15 hours
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 course
Track 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.

Practice algorithms

All Rights Reserved.