DEV Community

Wenqi Jiang
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]
]

Enter fullscreen mode Exit fullscreen mode

Output


[
    [-1, 2],
    [2, 1],
    [7, 3],
    [5, 1]
]

Enter fullscreen mode Exit fullscreen mode

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.

Enter fullscreen mode Exit fullscreen mode


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);
    }
}


Enter fullscreen mode Exit fullscreen mode

Discussion (0)