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.

[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]
]

[
[-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 * fraction2) - (fraction2 * fraction1));
for (int[] fraction : fractions) {
int a = fraction, b = fraction;
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()];
int index = 0;
for (int[] answer : set) {