# 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:

1. 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.

1. 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.

1. 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.

1. 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
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
// 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:
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:
vector calcEquation(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)>();
}

// 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;
}
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;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]