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.

Solution

To solve the problem, we observe that

  • given an equation a/b = n > 0 we also know b/a = 1/n.
  • given two equations a/b=n b/c=m, by transitivity, a/c=(a/b)(b/c)=nm.

For each query (a/b), we wish to find a path from dividend(a) to divisor(b) and multiply the quotients along the way to find the final answer. If no such path exists, then we can return -1.0.

We will use aggregated backtracking to find the answer to each query.

Implementation

1  def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
2      graph = defaultdict(list)
3      for i, [dividend, divisor] in enumerate(equations):
4          graph[dividend].append((divisor, values[i]))
5          graph[divisor].append((dividend, 1/values[i]))
6      
7      def divide(dividend, divisor, visited):
8          if dividend == divisor:
9              return 1
10          for new_dividend, multiplier in graph[dividend]:
11              if new_dividend not in visited:
12                  visited.add(new_dividend)
13                  ans = divide(new_dividend, divisor, visited)
14                  if ans > 0:
15                      return ans*multiplier
16                  visited.remove(new_dividend)
17          return -1
18      
19      res = []
20      for query in queries:
21          if graph[query[0]] == [] or graph[query[1]] == []:
22              res.append(-1)
23          else:
24              visited = set()
25              visited.add(query[0])
26              res.append(divide(query[0], query[1], visited))
27      return res
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Solution Implementation


Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄