Simplified fractions

Math String Number Theory

69.6% acceptance

Feb 25, 2026

442

Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. You can return the answer in any order.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn simplified_fractions(n: i32) -> Vec<String> {
    fn gcd(a: i32, b: i32) -> i32 { if b == 0 { a } else { gcd(b, a % b) } }
    let mut result = vec![];
    for q in 2..=n {
      for p in 1..q {
        if gcd(p, q) == 1 {
          result.push(format!("{}/{}", p, q));
        }
      }
    }
    result
  }
}