304 North Cardinal St.
Dorchester Center, MA 02124

# Evaluate Division LeetCode Solution

## Problem – Evaluate Division LeetCode Solution

You are given an array of variable pairs `equations` and an array of real numbers `values`, where `equations[i] = [Ai, Bi]` and `values[i]` represent the equation `Ai / Bi = values[i]`. Each `Ai` or `Bi` is a string that represents a single variable.

You are also given some `queries`, where `queries[j] = [Cj, Dj]` represents the `jth` query where you must find the answer for `Cj / Dj = ?`.

Return the answers to all queries. If a single answer cannot be determined, return `-1.0`.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:

``````Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation:
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]``````

Example 2:

``````Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]``````

Example 3:

``````Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]``````

Constraints:

• `1 <= equations.length <= 20`
• `equations[i].length == 2`
• `1 <= Ai.length, Bi.length <= 5`
• `values.length == equations.length`
• `0.0 < values[i] <= 20.0`
• `1 <= queries.length <= 20`
• `queries[i].length == 2`
• `1 <= Cj.length, Dj.length <= 5`
• `Ai, Bi, Cj, Dj` consist of lower case English letters and digits.

### Evaluate Division LeetCode Solution in C++

``````class Solution {
public:
void dfs(string start,string end,map<string,double>& mp,map<string,vector<string>>& graph,double& val,map<string,int>& visited,bool& found){
visited[start]=1;

if(found==true)
return ;
for(auto child:graph[start]){
if(visited[child]!=1){
// cout<<start<<" "<<child<<"\n";
val*=mp[start+"->"+child];
if(end==child){
// cout<<end<<" -- "<<child<<"\n";
found=true;
return ;
}
dfs(child,end,mp,graph,val,visited,found);
if(found==true){
return ;
}
else{
val/=mp[start+"->"+child];
}
}
}

}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
vector<double> ans;
map<string,double> mp;
map<string,vector<string>> graph;
for(int i=0;i<equations.size();i++){
string u=equations[i];
string v=equations[i];
mp[u+"->"+v]=values[i];
mp[v+"->"+u]=1/values[i];
graph[u].push_back(v);
graph[v].push_back(u);
}
for(int i=0;i<queries.size();i++){
string start=queries[i];
string end=queries[i];
if(graph.find(start)==graph.end()||graph.find(end)==graph.end()){
ans.push_back(-1);
}
else{
// ans.push_back(1);
double val=1;
map<string,int> visited;
bool found=false;
if(start==end){
found=true;
}
else
dfs(start,end,mp,graph,val,visited,found);
if(found==true)
ans.push_back(val);
else
ans.push_back(-1);

}
}
return ans;
}
};
``````

### Evaluate Division LeetCode Solution in Python

``````class Solution(object):
def calcEquation(self, equations, values, queries):

graph = {}

def build_graph(equations, values):
def add_edge(f, t, value):
if f in graph:
graph[f].append((t, value))
else:
graph[f] = [(t, value)]

for vertices, value in zip(equations, values):
f, t = vertices

def find_path(query):
b, e = query

if b not in graph or e not in graph:
return -1.0

q = collections.deque([(b, 1.0)])
visited = set()

while q:
front, cur_product = q.popleft()
if front == e:
return cur_product
for neighbor, value in graph[front]:
if neighbor not in visited:
q.append((neighbor, cur_product*value))

return -1.0

build_graph(equations, values)
return [find_path(q) for q in queries]
``````

### Evaluate Division LeetCode Solution in Java

``````    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
HashMap<String, ArrayList<String>> pairs = new HashMap<String, ArrayList<String>>();
HashMap<String, ArrayList<Double>> valuesPair = new HashMap<String, ArrayList<Double>>();
for (int i = 0; i < equations.length; i++) {
String[] equation = equations[i];
if (!pairs.containsKey(equation)) {
pairs.put(equation, new ArrayList<String>());
valuesPair.put(equation, new ArrayList<Double>());
}
if (!pairs.containsKey(equation)) {
pairs.put(equation, new ArrayList<String>());
valuesPair.put(equation, new ArrayList<Double>());
}
}

double[] result = new double[queries.length];
for (int i = 0; i < queries.length; i++) {
String[] query = queries[i];
result[i] = dfs(query, query, pairs, valuesPair, new HashSet<String>(), 1.0);
if (result[i] == 0.0) result[i] = -1.0;
}
return result;
}

private double dfs(String start, String end, HashMap<String, ArrayList<String>> pairs, HashMap<String, ArrayList<Double>> values, HashSet<String> set, double value) {
if (set.contains(start)) return 0.0;
if (!pairs.containsKey(start)) return 0.0;
if (start.equals(end)) return value;

ArrayList<String> strList = pairs.get(start);
ArrayList<Double> valueList = values.get(start);
double tmp = 0.0;
for (int i = 0; i < strList.size(); i++) {
tmp = dfs(strList.get(i), end, pairs, values, set, value*valueList.get(i));
if (tmp != 0.0) {
break;
}
}
set.remove(start);
return tmp;
}
``````
##### Evaluate Division LeetCode Solution Review:

In our experience, we suggest you solve this Evaluate Division LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Evaluate Division LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Evaluate Division LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions