# Solution For Evaluate Division

Evaluate Division is a problem on leetcode that involves computing the division of two given numbers and storing the result in a graph. The graph can then be used to answer queries about the division of two numbers that are not directly connected.

The following is a detailed solution for the Evaluate Division problem on leetcode:

- Create a graph using a dictionary:

The first step is to create a graph that contains all the given pair-wise divisions. The graph can be represented as a dictionary where the keys are the nodes (strings) and the corresponding values are dictionaries that contain the neighbor nodes and their respective weights (floats). This can be achieved using the following code:

`graph = {}`

for dividend, divisor, quotient in equations:

if dividend not in graph:

graph[dividend] = {}

if divisor not in graph:

graph[divisor] = {}

graph[dividend][divisor] = quotient

graph[divisor][dividend] = 1 / quotient

This code loops through the given equations and for each equation creates an entry in the dictionary for each of the nodes (if they don’t already exist). It then adds the quotient as the weight of the directed edge from the dividend to the divisor and its inverse as the weight of the directed edge from the divisor to the dividend.

- Implement DFS algorithm:

Next, we implement a DFS algorithm to traverse the graph and find the quotient between the two nodes. This can be achieved using the following code:

`def dfs(start, end, visited, graph):`

if start not in graph or end not in graph:

return -1.0

if start == end:

return 1.0

visited.add(start)

for neighbor in graph[start]:

if neighbor not in visited:

quotient = graph[start][neighbor]
temp = dfs(neighbor, end, visited, graph)

if temp != -1.0:

return quotient * temp

return -1.0

This code takes in the start node, end node, a set of visited nodes and the graph as inputs. It first checks if the start and end nodes exist in the graph and returns -1.0 if either of them don’t exist. It then checks if the start and end nodes are the same and returns 1.0 if they are.

If the start and end nodes are not the same, it adds the start node to the set of visited nodes and loops through all its neighbors. For each neighbor, it checks if it has not already been visited and finds the quotient between start and neighbor. It then calls the dfs function recursively with the neighbor as the start node, the end node, and the updated set of visited nodes.

If the recursion returns a value other than -1.0, it multiplies the quotient by this value and returns it. If all neighbors have been visited and the end node has not been found, it returns -1.0.

- Return the results:

Finally, we call the dfs function for each query and return the results in a list. This can be achieved using the following code:

```
results = []
for query in queries:
```

results.append(dfs(query[0], query[1], set(), graph))

This loops through the given queries and for each query, it calls the dfs function with the start and end nodes and an empty set of visited nodes. It then appends the result to a list of results and returns it.

- Complete solution:

Here is the complete solution in Python:

“`

class Solution:

def calcEquation(self, equations, values, queries):

graph = {}

for (dividend, divisor), quotient in zip(equations, values):

if dividend not in graph:

graph[dividend] = {}

if divisor not in graph:

graph[divisor] = {}

graph[dividend][divisor] = quotient

graph[divisor][dividend] = 1 / quotient

```
def dfs(start, end, visited, graph):
if start not in graph or end not in graph:
return -1.0
if start == end:
return 1.0
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
quotient = graph[start][neighbor]
temp = dfs(neighbor, end, visited, graph)
if temp != -1.0:
return quotient * temp
return -1.0
results = []
for query in queries:
results.append(dfs(query[0], query[1], set(), graph))
return results
```

“`

This solution passes all test cases on leetcode.

## Step by Step Implementation For Evaluate Division

class Solution { public double[] calcEquation(String[][] equations, double[] values, String[][] queries) { // create a graph where each node is an equation and each edge // represents a value Map> graph = new HashMap<>(); for (int i = 0; i < equations.length; i++) { String[] equation = equations[i]; // get the value of the edge double value = values[i]; // get the two nodes for the edge String node1 = equation[0]; String node2 = equation[1]; // add the edge to the graph graph.computeIfAbsent(node1, k -> new HashMap<>()).put(node2, value); graph.computeIfAbsent(node2, k -> new HashMap<>()).put(node1, 1.0 / value); } // create an array to store the results double[] result = new double[queries.length]; // loop through each query for (int i = 0; i < queries.length; i++) { // get the two nodes for the query String[] query = queries[i]; String node1 = query[0]; String node2 = query[1]; // if the graph doesn't contain either node, the result is -1.0 if (!graph.containsKey(node1) || !graph.containsKey(node2)) { result[i] = -1.0; } else { // otherwise, use a depth first search to find the value result[i] = dfs(graph, node1, node2, new HashSet<>()); } } return result; } // depth first search helper function private double dfs(Map > graph, String start, String end, Set visited) { // if the start node is the same as the end node, the result is 1.0 if (start.equals(end)) { return 1.0; } // mark the start node as visited visited.add(start); // get the map of edges for the start node Map edges = graph.get(start); // loop through each edge for (Map.Entry edge : edges.entrySet()) { // get the node at the end of the edge String node = edge.getKey(); // if the node has not been visited if (!visited.contains(node)) { // recursively call depth first search with the end node double result = dfs(graph, node, end, visited); // if the result is not -1.0, return the result if (result != -1.0) { return result * edge.getValue(); } } } // if there is no valid path, return -1.0 return -1.0; } }

class Solution: def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]: # build a graph using the equations and values graph = {} for i in range(len(equations)): x, y = equations[i] val = values[i] if x in graph and y in graph[x]: graph[x][y] = val graph[y][x] = 1/val elif x not in graph and y not in graph: graph[x] = {} graph[x][y] = val graph[y] = {} graph[y][x] = 1/val elif x in graph and y not in graph: graph[y] = {} graph[y][x] = 1/val graph[x][y] = val elif y in graph and x not in graph: graph[x] = {} graph[x][y] = val graph[y][x] = 1/val # use dfs to find the product of the edges between two nodes def dfs(x, y, visited): if x == y: return 1.0 for node in graph[x]: if node not in visited: visited.add(node) temp = dfs(node, y, visited) if temp: return temp * graph[x][node] return -1.0 # iterate through all queries and find the product for each ans = [] for x, y in queries: visited = set() if x not in graph or y not in graph: ans.append(-1.0) else: ans.append(dfs(x, y, visited)) return ans

var evaluateDivision = function(equations, values, queries) { // create a map of the equations let map = {}; for (let i = 0; i < equations.length; i++) { const [a, b] = equations[i]; // if the key does not exist, create it and set its value to an empty array if (!map[a]) { map[a] = []; } // push the equation and its corresponding value into the map map[a].push([b, values[i]]); // do the same for the inverse equation if (!map[b]) { map[b] = []; } map[b].push([a, 1/values[i]]); } // helper function to find the value of an equation function findValue(start, end, map, visited) { // if the start node does not exist in the map, return -1 if (!map[start]) { return -1; } // if the start node is the same as the end node, return 1 if (start === end) { return 1; } // mark the start node as visited visited[start] = true; // get the array of equations from the map const equations = map[start]; // loop through the equations for (let i = 0; i < equations.length; i++) { const [node, value] = equations[i]; // if the node has not been visited yet if (!visited[node]) { // recursively call the helper function with the node and the end node const res = findValue(node, end, map, visited); // if the result is not -1, return the value of the equation multiplied by the result if (res !== -1) { return res * value; } } } // if no equation is found, return -1 return -1; } // result array const res = []; // loop through the queries for (let i = 0; i < queries.length; i++) { const [start, end] = queries[i]; // create an object to keep track of visited nodes const visited = {}; // call the helper function to find the value of the equation and push it into the result array res.push(findValue(start, end, map, visited)); } // return the result array return res; };

class Solution { public: vectorcalcEquation(vector > equations, vector & values, vector > queries) { // Create a graph using the equations and values unordered_map > graph; int n = equations.size(); for (int i = 0; i < n; i++) { string a = equations[i].first; string b = equations[i].second; double val = values[i]; if (!graph.count(a)) { graph[a] = unordered_map (); } if (!graph.count(b)) { graph[b] = unordered_map (); } graph[a][b] = val; graph[b][a] = 1.0 / val; } // DFS to find the path from a to b vector result; for (auto& query : queries) { string a = query.first; string b = query.second; if (!graph.count(a) || !graph.count(b)) { result.push_back(-1.0); continue; } unordered_set visited; double val = dfs(graph, a, b, visited); if (val == 0.0) { result.push_back(-1.0); } else { result.push_back(val); } } return result; } double dfs(unordered_map >& graph, string& a, string& b, unordered_set & visited) { if (a == b) { return 1.0; } visited.insert(a); for (auto& neighbor : graph[a]) { if (visited.count(neighbor.first)) { continue; } double val = dfs(graph, neighbor.first, b, visited); if (val != 0.0) { return val * neighbor.second; } } return 0.0; } };

public class Solution { public double[] CalcEquation(string[,] equations, double[] values, string[,] queries) { // create a graph where each node is an equation and each edge is a value var graph = new Dictionary>(); for (int i = 0; i < equations.GetLength(0); i++) { string eq1 = equations[i,0], eq2 = equations[i,1]; double val = values[i]; if (!graph.ContainsKey(eq1)) graph[eq1] = new List<(string, double)>(); if (!graph.ContainsKey(eq2)) graph[eq2] = new List<(string, double)>(); graph[eq1].Add((eq2, val)); graph[eq2].Add((eq1, 1.0 / val)); } // for each query, do a BFS to find the path from the first equation to the second equation // if a path exists, the product of the values along the path is the answer // otherwise, the answer is -1.0 var ans = new double[queries.GetLength(0)]; for (int i = 0; i < queries.GetLength(0); i++) { string eq1 = queries[i,0], eq2 = queries[i,1]; if (!graph.ContainsKey(eq1) || !graph.ContainsKey(eq2)) { ans[i] = -1.0; continue; } var visited = new HashSet (); var queue = new Queue<(string, double)>(); queue.Enqueue((eq1, 1.0)); while (queue.Count > 0) { var (node, val) = queue.Dequeue(); if (node == eq2) { ans[i] = val; break; } visited.Add(node); foreach (var (neighbor, neighborVal) in graph[node]) { if (!visited.Contains(neighbor)) { queue.Enqueue((neighbor, val * neighborVal)); } } } if (ans[i] == 0) ans[i] = -1.0; } return ans; } }