Simplified Fractions — Solution in Python, Java & C++
Simplified Fractions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on strings and math.
Simplified Fractions is a medium coding problem on strings, math and number theory, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Math, Number Theory
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer n, return every fraction strictly between 0 and 1 whose denominator is at most n and which is in lowest terms (numerator and denominator share no common factor above 1).
Write each fraction as "numerator/denominator", and list them in increasing order of value. Each value appears once, so 2/4 is not listed separately from 1/2.
Example 1
Input: n = 2
Output: ["1/2"]
Example 2
Input: n = 3
Output: ["1/3","1/2","2/3"]
Example 3
Input: n = 4
Output: ["1/4","1/3","1/2","2/3","3/4"]
Explanation: 2/4 is the same value as 1/2 and is not in lowest terms.
Constraints
1 <= n <= 100
Hints for Simplified Fractions
Hint 1
Try every denominator
bfrom 2 tonand every numeratorafrom 1 tob - 1.Hint 2
a/bis in lowest terms exactly whengcd(a, b) == 1; each value between 0 and 1 has exactly one such form.Hint 3
To sort by value without floating point, compare
a/b < c/dasa*d < c*b.
How to solve Simplified Fractions
Enumerate all pairs a < b <= n with gcd(a, b) = 1, then sort them by value using cross-multiplication.
Approach
- For each
bfrom 2 tonand eachafrom 1 tob - 1, keep the pair ifgcd(a, b) == 1. - Sort the kept pairs:
(a, b)comes before(c, d)whena * d < c * b. - Format each pair as
"a/b"and return the list.
Why it works
Every rational in (0, 1) with denominator at most n has a unique lowest-terms representation a/b, and its denominator is at most n too, so the coprime pairs list each value exactly once. Distinct reduced fractions have distinct values, so the order is fully determined, and cross-multiplying positive denominators preserves the comparison exactly. (The result is the Farey sequence of order n without its endpoints.)
Complexity
- Time —
O(n² log n) — about 0.3·n² fractions, each needing a gcd, then a sort - Space —
O(n²) for the output
Pitfalls
- Listing non-reduced duplicates like
2/4next to1/2. n = 1has no fractions: return an empty list.- Sorting by floating-point quotient works for these sizes, but cross-multiplication is exact and just as short.
Reference solution
Python
from typing import List
from math import gcd
from functools import cmp_to_key
def simplifiedFractions(n: int) -> List[str]:
pairs = [(a, b) for b in range(2, n + 1) for a in range(1, b) if gcd(a, b) == 1]
pairs.sort(key=cmp_to_key(lambda p, q: p[0] * q[1] - q[0] * p[1]))
return [str(a) + "/" + str(b) for a, b in pairs]Java
static int sfGcd(int x, int y) {
while (y != 0) {
int t = x % y;
x = y;
y = t;
}
return x;
}
public static String[] simplifiedFractions(int n) {
List<int[]> pairs = new ArrayList<>();
for (int b = 2; b <= n; b++) {
for (int a = 1; a < b; a++) if (sfGcd(a, b) == 1) pairs.add(new int[] {a, b});
}
pairs.sort((p, q) -> Integer.compare(p[0] * q[1], q[0] * p[1]));
String[] out = new String[pairs.size()];
for (int i = 0; i < out.length; i++) out[i] = pairs.get(i)[0] + "/" + pairs.get(i)[1];
return out;
}C++
static int sfGcd(int x, int y) { while (y) { int t = x % y; x = y; y = t; } return x; }
vector<string> simplifiedFractions(int n) {
vector<pair<int, int>> pairs;
for (int b = 2; b <= n; b++) {
for (int a = 1; a < b; a++) if (sfGcd(a, b) == 1) pairs.push_back({a, b});
}
sort(pairs.begin(), pairs.end(), [](const pair<int, int>& p, const pair<int, int>& q) {
return p.first * q.second < q.first * p.second;
});
vector<string> out;
for (auto& p : pairs) out.push_back(to_string(p.first) + "/" + to_string(p.second));
return out;
}JavaScript
var simplifiedFractions = function(n) {
var gcd = function(x, y) {
while (y !== 0) {
var t = x % y;
x = y;
y = t;
}
return x;
};
var pairs = [];
for (var b = 2; b <= n; b++) {
for (var a = 1; a < b; a++) if (gcd(a, b) === 1) pairs.push([a, b]);
}
pairs.sort(function(p, q) { return p[0] * q[1] - q[0] * p[1]; });
return pairs.map(function(p) { return p[0] + "/" + p[1]; });
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings