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:
Solutions
Solution 1
PythonJavaC++GoTypeScriptRust
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
](code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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)
}(code-box)
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);
}(code-box)
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
}
}(code-box)
