## DEV Community is a community of 797,169 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Wenqi Jiang

Posted on

# [Binary Search]Unique Fractions

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` becomes `4 / 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` where `n` is the length of `fractions`

### 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};
}
int[][] ans = new int[set.size()][2];
int index = 0;
for (int[] answer : set) {