Question

1447. Simplified Fractions

中文文档

Description

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.

 

Example 1:

Input: n = 2
Output: ["1/2"]
Explanation: "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.

Example 2:

Input: n = 3
Output: ["1/2","1/3","2/3"]

Example 3:

Input: n = 4
Output: ["1/2","1/3","1/4","2/3","3/4"]
Explanation: "2/4" is not a simplified fraction because it can be simplified to "1/2".

 

Constraints:

• 1 <= n <= 100

Solutions

Solution 1

class Solution:
  def simplifiedFractions(self, n: int) -> List[str]:
    return [
      f'{i}/{j}'
      for i in range(1, n)
      for j in range(i + 1, n + 1)
      if gcd(i, j) == 1
    ]

class Solution {
  public List<String> simplifiedFractions(int n) {
    List<String> ans = new ArrayList<>();
    for (int i = 1; i < n; ++i) {
      for (int j = i + 1; j < n + 1; ++j) {
        if (gcd(i, j) == 1) {
          ans.add(i + "/" + j);
        }
      }
    }
    return ans;
  }

  private int gcd(int a, int b) {
    return b > 0 ? gcd(b, a % b) : a;
  }
}

class Solution {
public:
  vector<string> simplifiedFractions(int n) {
    vector<string> ans;
    for (int i = 1; i < n; ++i) {
      for (int j = i + 1; j < n + 1; ++j) {
        if (__gcd(i, j) == 1) {
          ans.push_back(to_string(i) + "/" + to_string(j));
        }
      }
    }
    return ans;
  }
};

func simplifiedFractions(n int) (ans []string) {
  for i := 1; i < n; i++ {
    for j := i + 1; j < n+1; j++ {
      if gcd(i, j) == 1 {
        ans = append(ans, strconv.Itoa(i)+"/"+strconv.Itoa(j))
      }
    }
  }
  return ans
}

func gcd(a, b int) int {
  if b == 0 {
    return a
  }
  return gcd(b, a%b)
}

function simplifiedFractions(n: number): string[] {
  const ans: string[] = [];
  for (let i = 1; i < n; ++i) {
    for (let j = i + 1; j < n + 1; ++j) {
      if (gcd(i, j) === 1) {
        ans.push(`${i}/${j}`);
      }
    }
  }
  return ans;
}

function gcd(a: number, b: number): number {
  return b === 0 ? a : gcd(b, a % b);
}

impl Solution {
  fn gcd(a: i32, b: i32) -> i32 {
    match b {
      0 => a,
      _ => Solution::gcd(b, a % b),
    }
  }

  pub fn simplified_fractions(n: i32) -> Vec<String> {
    let mut res = vec![];
    for i in 1..n {
      for j in i + 1..=n {
        if Solution::gcd(i, j) == 1 {
          res.push(format!("{}/{}", i, j));
        }
      }
    }
    res
  }
}