## Algorithm

Problem Name: 399. Evaluate Division

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.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#define DUMP(OP, OP1, OP2) do { } while (0)

double math(int k, double op1, double op2) {
DUMP(k, op1, op2);
switch(k) {
case 1:
op1 = 1.0;
break;
case 2:
op1 = op2;
break;
case 3:
op1 = 1 / op2;
break;
case 4:
case 5:
op1 = op1 * op2;
break;
case 6:
case 7:
op1 = op1 / op2;
break;
}
return op1;
}
int match(char **strs, char *fm, char *fz) {
int x00, x01, x10, x11;
int k = 0;

x00 = !strcmp(fm, strs[0]);
x01 = !strcmp(fm, strs[1]);
x10 = !strcmp(fz, strs[0]);
x11 = !strcmp(fz, strs[1]);

if ((!x00 && !x01 && !x10 && !x11) ||
(x00 && x01 && !x10) ||
(x10 && x11 && !x00)){
k = 0; // no match or useless match
} else if ((x00 && x10) || (x01 && x11)) {
k = 1;  // 1
} else if (x00 && x11) {
k = 2;  // equal
} else if (x01 && x10) {
k = 3;  // reverse
} else if (x00) {
k = 4;  // multiply
} else if (x11) {
k = 5;
} else if (x01) {
k = 6;  // divide
} else if (x10) {
k = 7;
}
return k;
}
int calc(int *visited, double *d, char ***equa, double *val, int rowsz, char *fm, char *fz) {
int i, k, x;
​
for (i = 0; i  <  rowsz; i ++) {
if (visited[i] == 0) {
k = match(equa[i], fm, fz);
if (k >= 1 && k  < = 3) {
*d = math(k, *d, val[i]);
return 1;
} else if (k != 0) {
visited[i] = 1;
if (k == 4) {
x = calc(visited, d, equa, val, rowsz, equa[i][1], fz);
} else if (k == 5) {
x = calc(visited, d, equa, val, rowsz, fm, equa[i][0]);
} else if (k == 6) {
x = calc(visited, d, equa, val, rowsz, equa[i][0], fz);
} else /*if (k == 7)*/ {
x = calc(visited, d, equa, val, rowsz, fm, equa[i][1]);
}
visited[i] = 0;
if (x) {
*d = math(k, *d, val[i]);
return 1;
}
}
}
}
return 0;
}
double* calcEquation(char*** equations, int equationsRowSize, int equationsColSize, double* values, int valuesSize, char*** queries, int queriesRowSize, int queriesColSize, int* returnSize) {
int *visited;
double *results, d;

int i;

results = malloc(queriesRowSize * sizeof(double));
visited = calloc(equationsRowSize, sizeof(int));
//assert(result && visited);

*returnSize = queriesRowSize;

for (i = 0; i  <  queriesRowSize; i ++) {
d = -1.0;
calc(visited, &d, equations, values, equationsRowSize, queries[i][0], queries[i][1]);
results[i] = d;
}

free(visited);

return results;
}
``````
Copy The Code &

Input

cmd
equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]

Output

cmd
[6.00000,0.50000,-1.00000,1.00000,-1.00000]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
private:
unordered_map calcEquation(vector<pair& values, vector<pairres;
for(int i = 0; i  <  values.size(); i++){
auto p = equations[i];
weight[p.first][p.second] = values[i];
weight[p.second][p.first] = 1 / values[i];
graph[p.first].push_back(p.second);
graph[p.second].push_back(p.first);
}
for(int i = 0; i  <  queries.size(); i++){
unordered_setvisited;
deque < pair calcEquation(vector<pair& values, vector<pairres;
unordered_mapvisited;
queue<pair``````
``` Copy The Code & Input x – + cmd equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] Output x – + cmd [6.00000,0.50000,-1.00000,1.00000,-1.00000] ```
``` #3 Code Example with Java Programming Code - Java Programming class Solution { public double[] calcEquation(List(); Map valueMap = new HashMap<>(); for (int i = 0; i < equations.size(); i++) { String equation = equations.get(i).get(0) + "/" + equations.get(i).get(1); connectionMap.computeIfAbsent(equations.get(i).get(0), k -> new HashSet < >()) .add(equations.get(i).get(1)); connectionMap.computeIfAbsent(equations.get(i).get(1), k -> new HashSet<>()) .add(equations.get(i).get(0)); valueMap.put(equation, values[i]); } for (int i = 0; i < queries.size(); i++) { String source = queries.get(i).get(0); String target = queries.get(i).get(1); double[] res = {-1.0}; dfs(connectionMap, valueMap, source, target, new HashSet < >(), res, 1.0); ans[i] = res[0]; } return ans; } private void dfs(Map < String, Set valueMap, String source, String target, Set visited, double[] res, double currVal) { if (source.equals(target) && ( connectionMap.containsKey(source) || connectionMap.containsKey(target)) ) { res[0] = currVal; return; } for (String connection : connectionMap.getOrDefault(source, new HashSet < >())) { if (!visited.contains(connection)) { visited.add(connection); double newwCurrVal = currVal * ( valueMap.containsKey(source + "/" + connection) ? valueMap.get(source + "/" + connection) : (1 / valueMap.get(connection + "/" + source)) ); dfs(connectionMap, valueMap, connection, target, visited, res, newwCurrVal); } } } } Copy The Code & Input x – + cmd equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] Output x – + cmd [3.75000,0.40000,5.00000,0.20000] #4 Code Example with Javascript Programming Code - Javascript Programming const calcEquation = function(equations, values, queries) { const m = {}; for (let i = 0; i < values.length; i++) { if (!m.hasOwnProperty(equations[i][0])) m[equations[i][0]] = {}; if (!m.hasOwnProperty(equations[i][1])) m[equations[i][1]] = {}; m[equations[i][0]][equations[i][1]] = values[i]; m[equations[i][1]][equations[i][0]] = 1 / values[i]; } const r = []; for (let i = 0; i < queries.length; i++) { r[i] = dfs(queries[i][0], queries[i][1], 1, m, []); } return r; }; function dfs(s, t, r, m, seen) { if (!m.hasOwnProperty(s) || !hsetAdd(seen, s)) return -1; if (s === t) return r; let next = m[s]; for (let c of Object.keys(next)) { let result = dfs(c, t, r * next[c], m, seen); if (result !== -1) return result; } return -1; } function hsetAdd(arr, el) { if (arr.indexOf(el) === -1) { arr.push(el); return true; } else { return false; } } Copy The Code & Input x – + cmd equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] Output x – + cmd [3.75000,0.40000,5.00000,0.20000] #5 Code Example with Python Programming Code - Python Programming class Solution: def calcEquation(self, equations, values, queries): def explore(x, y, r, q): results[(x, y)] = r for z in edges[y]: if z not in q: results[(x, z)], results[(z, x)] = r * vals[(y, z)], 1 / (r * vals[(y, z)]) explore(x, z, r * vals[(y, z)], q | {z}) edges, vals, visited, results, res = collections.defaultdict(set), {}, set(), {}, [] for i, eq in enumerate(equations): edges[eq[0]].add(eq[1]) edges[eq[1]].add(eq[0]) vals[(eq[0], eq[1])], vals[(eq[1], eq[0])] = values[i], 1 / values[i] for i, eq in enumerate(equations): for p in eq: if p not in visited: visited.add(p) explore(p, p, 1.0, {p}) for q in queries: if (q[0], q[1]) in results: res += results[(q[0], q[1])], else: res += -1.0, return res Copy The Code & Input x – + cmd equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]] Output x – + cmd [0.50000,2.00000,-1.00000,-1.00000] #6 Code Example with C# Programming Code - C# Programming using System.Collections.Generic; namespace LeetCode { public class _0399_EvaluateDivision { public double[] CalcEquation(IList < IList parents = new Dictionary(); public Node Find(string index) { if (!parents.ContainsKey(index)) parents.Add(index, new Node(index, 1.0)); else if (parents[index].ParentIndex != index) { var value = parents[index].Value; var parent = Find(parents[index].ParentIndex); parents[index] = new Node(parent.ParentIndex, value * parent.Value); } return parents[index]; } public bool Exist(string index) { return parents.ContainsKey(index); } public void Union(string index1, string index2, double value) { var pIndex1 = Find(index1); var pIndex2 = Find(index2); if (pIndex1.ParentIndex != pIndex2.ParentIndex) parents[pIndex1.ParentIndex] = new Node(pIndex2.ParentIndex, value * pIndex2.Value / pIndex1.Value); } } public class Node { public Node(string parentIndex, double value) { ParentIndex = parentIndex; Value = value; } public string ParentIndex { get; set; } public double Value { get; set; } } } } Copy The Code & Input x – + cmd equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]] Output x – + cmd [0.50000,2.00000,-1.00000,-1.00000] Advertisements (adsbygoogle = window.adsbygoogle || []).push({}); Demonstration ```
``` #398 Leetcode Random Pick Index Solution in C, C++, Java, JavaScript, Python, C# Leetcode #400 Leetcode Nth Digit Solution in C, C++, Java, JavaScript, Python, C# Leetcode ```
``` ```