1447. Simplified Fractions
Explanation
To solve this problem, we can iterate over all possible numerators from 1 to n-1 and for each numerator, iterate over all possible denominators from numerator+1 to n. We check if the numerator and denominator are coprime (i.e., their greatest common divisor is 1). If they are coprime, we add the simplified fraction to our result list.
Algorithm
- Initialize an empty list
resultto store the simplified fractions. - Iterate
numeratorfrom 1 to n-1.- For each numerator, iterate
denominatorfrom numerator+1 to n.- If gcd(numerator, denominator) is 1, then add the simplified fraction to
result.
- If gcd(numerator, denominator) is 1, then add the simplified fraction to
- For each numerator, iterate
- Return the
result.
Time Complexity
The time complexity of this algorithm is O(n^2) where n is the input integer.
Space Complexity
The space complexity is O(1) excluding the space required to store the result.
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> simplifiedFractions(int n) {
List<String> result = new ArrayList<>();
for (int numerator = 1; numerator < n; numerator++) {
for (int denominator = numerator + 1; denominator <= n; denominator++) {
if (gcd(numerator, denominator) == 1) {
result.add(numerator + "/" + denominator);
}
}
}
return result;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.