Evaluate Division in Java
The problem involves a system of equations and queries involving real numbers. Equations are represented as pairs of variables, and queries are represented as strings. The objective is to evaluate and return the results of all queries, with -1.0 returned if undefined variables cannot be determined. The input is guaranteed to be valid.
Example 1:
![Evaluate Division in Java](https://static.tutorialandexample.com/java/evaluate-division-in-java1.png)
Input: equations = {{"a", "b"}, {"a", "c"}}
values = {2.0, 3.0} queries = {{"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}, {"x", "x"}}
Output: [6.0, 0.5, -1.0, 1.0, -1.0]
Explanation:
Query: ["a", "c"]
Direction: a -> b -> c; Outcome: 2.0 * 3.0 = 6.0
Query: ["b", "a"]
Route: b -> a Finding: 0.5 / 2.0 = 1.0
Query: ["a", "e"]
Since variable e is undefined, -1.0 is the outcome.
Query: ["a", "a"]
Involves a self-loop on node a, with a 1.0 outcome.
Query: ["x", "x"]
Since variables x are undefined, -1.0 is the outcome.
Using Naive Approach
The naive approach evaluates query results based on equations and values using a recursive depth-first search (DFS) to traverse a graph. The code constructs a graph with variables as nodes and edges representing values between them. For each query, the code uses DFS to traverse the graph, calculating the result of dividing one variable by another (A / C) for each query. If either variable is not present, the result is set to -1.0. If they are the same or different, the code recursively explores neighbours and calculates the result. The recursion traverses the graph to find a path with a set of seen variables to avoid cycles. The results are stored in an array, and the main method prints the array of results for the given queries.
Here's an implementation of evaluating division using a naive approach:
FileName:NaiveSolution.java
import java.util.*; public class NaiveSolution { public static void main(String[] args) { NaiveSolution solution = new NaiveSolution(); List> equations = new ArrayList<>(); equations.add(Arrays.asList("a", "b")); equations.add(Arrays.asList("b", "c")); double[] values = { 2.0, 3.0 }; List
> queries = new ArrayList<>(); queries.add(Arrays.asList("a", "c")); queries.add(Arrays.asList("b", "a")); queries.add(Arrays.asList("a", "e")); queries.add(Arrays.asList("a", "a")); queries.add(Arrays.asList("x", "x")); double[] result = solution.calcEquation(equations, values, queries); System.out.println(Arrays.toString(result)); } public double[] calcEquation(List
> equations, double[] values, List
> queries) { double[] ans = new double[queries.size()]; // Construct the graph. Map
> graph = new HashMap<>(); for (int i = 0; i < equations.size(); ++i) { final String A = equations.get(i).get(0); final String B = equations.get(i).get(1); graph.putIfAbsent(A, new HashMap<>()); graph.putIfAbsent(B, new HashMap<>()); graph.get(A).put(B, values[i]); graph.get(B).put(A, 1.0 / values[i]); } // Process each query. for (int i = 0; i < queries.size(); ++i) { final String A = queries.get(i).get(0); final String C = queries.get(i).get(1); if (!graph.containsKey(A) || !graph.containsKey(C)) ans[i] = -1.0; else ans[i] = divide(graph, A, C, new HashSet<>()); } return ans; } private double divide(Map > graph, final String A, final String C, Set seen) { // Base case: A and C are the same variable. if (A.equals(C)) return 1.0; seen.add(A); // Recursive case: Explore each neighbour B of A. for (final String B : graph.get(A).keySet()) { if (seen.contains(B)) continue; final double res = divide(graph, B, C, seen); // B / C if (res > 0) // valid result return graph.get(A).get(B) * res; // A / C = (A / B) * (B / C) } return -1.0; // invalid result } }
Output:
[6.0, 0.5, -1.0, 1.0, -1.0]
Complexity analysis: The code consists of three parts: constructing a graph, processing queries, and storing the graph. The construction process takes O(n) time, while the processing queries involve recursive traversal. The space complexity for storing the graph is O(n + V), where n is the number of equations and V is the number of distinct variables. The depth of the recursion for each query is limited by the number of distinct variables, and other data structures contribute to the space complexity. The overall time complexity is O(n + m * V), with the recursive traversal being the primary factor influencing the algorithm's efficiency.
Using Optimized Approach
The code implements an optimized solution for evaluating division operations using the Union-Find data structure. It efficiently handles equations, values, and queries using Union-Find to represent connected components in the graph. The code utilizes parent-child relationships and ratios. The main method creates an instance of the optimized solution, demonstrating its functionality with equations and queries.
Here's an implementation of evaluating division using an optimized approach:
FileName:OptimizedSolution.java
import java.util.*; public class OptimizedSolution { public static void main(String[] args) { OptimizedSolution solution = new OptimizedSolution(); List> equations = new ArrayList<>(); equations.add(Arrays.asList("a", "b")); equations.add(Arrays.asList("b", "c")); double[] values = { 2.0, 3.0 }; List
> queries = new ArrayList<>(); queries.add(Arrays.asList("a", "c")); queries.add(Arrays.asList("b", "a")); queries.add(Arrays.asList("a", "e")); queries.add(Arrays.asList("a", "a")); queries.add(Arrays.asList("x", "x")); double[] result = solution.calcEquation(equations, values, queries); System.out.println(Arrays.toString(result)); } public double[] calcEquation(List
> equations, double[] values, List
> queries) { UnionFind unionFind = new UnionFind(); // Construct the graph and perform union operations. for (int i = 0; i < equations.size(); ++i) { final String A = equations.get(i).get(0); final String B = equations.get(i).get(1); double value = values[i]; unionFind.union(A, B, value); } double[] ans = new double[queries.size()]; // Process queries. for (int i = 0; i < queries.size(); ++i) { final String A = queries.get(i).get(0); final String C = queries.get(i).get(1); ans[i] = unionFind.query(A, C); } return ans; } private static class UnionFind { private Map
parent; private Map ratio; public UnionFind() { parent = new HashMap<>(); ratio = new HashMap<>(); } public String find(String variable) { if (!parent.containsKey(variable)) { parent.put(variable, variable); ratio.put(variable, 1.0); return variable; } if (!parent.get(variable).equals(variable)) { String root = find(parent.get(variable)); ratio.put(variable, ratio.get(variable) * ratio.get(parent.get(variable))); parent.put(variable, root); } return parent.get(variable); } public void union(String A, String B, double value) { String rootA = find(A); String rootB = find(B); parent.put(rootA, rootB); ratio.put(rootA, value * ratio.get(B) / ratio.get(A)); } public double query(String A, String C) { if (!parent.containsKey(A) || !parent.containsKey(C)) return -1.0; String rootA = find(A); String rootC = find(C); if (!rootA.equals(rootC)) return -1.0; return ratio.get(A) / ratio.get(C); } } }
Output:
[6.0, 0.5, -1.0, 1.0, -1.0]
Complexity analysis: The optimized code has a time complexity of O(n * log n) due to union-find operations and query processing. The space complexity is O(n) for storing the Union-Find data structure, where n is the number of distinct variables in the equations. Other data structures contribute to O(m + n) space. The overall time complexity is dominated by union-find operations, resulting in O(n * log n) time complexity and O(n + m) space complexity. The optimized solution is more efficient than the naive approach, especially when dealing with large numbers of equations and queries.