Simplified Fractions

Medium
1295.

Simplified Fractions

Simplified Fractions is a medium coding problem on strings, math and number theory, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {string[]}
 */
var simplifiedFractions = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Try every denominator b from 2 to n and every numerator a from 1 to b - 1.

  2. Hint 2

    a/b is in lowest terms exactly when gcd(a, b) == 1; each value between 0 and 1 has exactly one such form.

  3. Hint 3

    To sort by value without floating point, compare a/b < c/d as a*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

  1. For each b from 2 to n and each a from 1 to b - 1, keep the pair if gcd(a, b) == 1.
  2. Sort the kept pairs: (a, b) comes before (c, d) when a * d < c * b.
  3. 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/4 next to 1/2.
  • n = 1 has 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