You are given a list of lists fractions
where each list contains [numerator, denominator]
which represents the number numerator / denominator
.
Return a new list of lists such that the numbers in fractions
are:
- In their most reduced terms. E.g.
8 / 6
becomes4 / 3
. - Any duplicate fractions that represent the same value are removed.
- Sorted in ascending order by their value.
- If the number is negative, the sign should go to the
numerator
(the input also follows this).
Constraints
-
n ≤ 100,000
wheren
is the length offractions
Example
fractions = [
[8, 4],
[2, 1],
[7, 3],
[14, 6],
[10, 2],
[-3, 6]
]
Output
[
[-1, 2],
[2, 1],
[7, 3],
[5, 1]
]
Explanation
Once we reduce the numbers they become [[2, 1], [2, 1], [7, 3], [7, 3], [5, 1], [-1, 2]].
The result then comes from deduping and sorting by value.
import java.util.*;
class Solution {
public int[][] solve(int[][] fractions) {
Set<int[]> set = new TreeSet<>(
(fraction1,
fraction2) -> (fraction1[0] * fraction2[1]) - (fraction2[0] * fraction1[1]));
for (int[] fraction : fractions) {
int a = fraction[0], b = fraction[1];
int gcd = gcd(Math.max(Math.abs(a), Math.abs(b)), Math.min(Math.abs(a), Math.abs(b)));
int[] result = new int[] {a / gcd, b / gcd};
set.add(result);
}
int[][] ans = new int[set.size()][2];
int index = 0;
for (int[] answer : set) {
ans[index++] = answer;
}
return ans;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
Top comments (0)