Math
String
Number Theory
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
Python3 Java C++ Go TypeScript Rust
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
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 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 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 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 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 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 )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 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 );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 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
}
}