Evaluate Division
Problem statement
You get a list of equations like a / b = 2.0, given as pairs of variable names in equations and their results in values. Then you get queries, each asking for c / d. Answer every query using only the equations you were given.
If a query can't be worked out — because a variable never appeared in any equation, or because the two variables are not linked through any chain of equations — its answer is -1.0. The input never contradicts itself and never divides by zero.
Think of it as converting between units when you only know some conversion rates: if 1 node = 2 vCPUs and 1 vCPU = 3 threads, how many threads is 1 node? And you can't answer anything about a unit you've never seen.
Examples
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: a / c = (a / b) × (b / c) = 2 × 3 = 6, and b / a is the flip of 2, which is 0.5. e and x never appear in any equation, so those queries are -1, even x / x; a / a is 1 because a is known.
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]
Explanation: a / c = 1.5 × 2.5 = 3.75 and c / b = 1 / 2.5 = 0.4. bc and cd are just two more variable names, so bc / cd = 5 and its flip is 0.2.
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]
Explanation: a / b is given as 0.5, and b / a is its flip, 2. Neither c nor x and y appear in the equations, so the last two queries can't be answered.
Hints
a / b = 2, draw a link from a to b with weight 2 — and what weight should the link from b back to a have?Approach
Optimal: Weighted union-find
Intuition
Put variables that are linked by equations into groups. Inside each group, pick one variable as the root, and store, for every variable, its value divided by the root's value. Then any query inside a group is easy: c / d = (c / root) / (d / root). Variables in different groups can't be compared, so the answer is -1.
A union-find (disjoint-set) keeps these groups. Each variable stores a parent and a weight, where weight[x] = x / parent[x]. find(x) walks up to the root, multiplying the weights, so it returns the root and x / root; on the way it points x straight at the root (path compression) so later finds are instant. For an equation a / b = v, if a and b are in different groups, attach a's root under b's root with the weight that keeps the equation true.
Steps
- For each equation
[a, b]with valuev:- Add
aandbif new (each is its own root with weight 1). find(a)gives rootraandwa = a / ra;find(b)givesrbandwb = b / rb.- If
ra != rb: setparent[ra] = rbandweight[ra] = v × wb / wa. (That isra / rb, becausea / b = v.)
- Add
- For each query
[c, d]:- If either is unknown, the answer is
-1. find(c)gives(rc, wc)andfind(d)gives(rd, wd). Ifrc != rd, the answer is-1; otherwise it iswc / wd.
- If either is unknown, the answer is
- Return the answers.
Dry run
Example 1: equations a / b = 2, b / c = 3.
| step | action | parent / weight after |
|---|---|---|
| a / b = 2 | roots a, b differ → parent[a] = b, weight[a] = 2 × 1 / 1 = 2 |
a → b (2) |
| b / c = 3 | roots b, c differ → parent[b] = c, weight[b] = 3 × 1 / 1 = 3 |
a → b (2), b → c (3) |
| query a / c | find(a): a → b → c, weight 2 × 3 = 6; find(c): c, weight 1 | answer 6 / 1 = 6 |
| query b / a | find(b) = (c, 3), find(a) = (c, 6) | answer 3 / 6 = 0.5 |
The unknown e and x give -1, and a / a gives 6 / 6 = 1.
Complexity
Time O((E + Q)·α(V)) - Each equation does one union and each query does two finds. With path compression, a find is close to O(1) on average (α is the inverse Ackermann function, at most 4 in practice). So the total is almost linear in equations plus queries. This wins when there are many queries on the same equations.
Space O(V) - We store one parent and one weight per variable. No adjacency list or queue is needed. The output list is not counted.
from typing import Dict, List, Tuple
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float],
queries: List[List[str]]) -> List[float]:
parent: Dict[str, str] = {}
weight: Dict[str, float] = {} # weight[x] = x / parent[x]
def find(x: str) -> Tuple[str, float]:
if parent[x] != x:
root, w = find(parent[x])
parent[x] = root
weight[x] *= w
return parent[x], weight[x]
for (a, b), v in zip(equations, values):
for x in (a, b):
if x not in parent:
parent[x] = x
weight[x] = 1.0
ra, wa = find(a)
rb, wb = find(b)
if ra != rb:
parent[ra] = rb
weight[ra] = v * wb / wa
answers = []
for c, d in queries:
if c not in parent or d not in parent:
answers.append(-1.0)
continue
rc, wc = find(c)
rd, wd = find(d)
answers.append(wc / wd if rc == rd else -1.0)
return answers
def fmt(xs: List[float]) -> str:
return "[" + ",".join(f"{x:.5f}" for x in xs) + "]"
if __name__ == "__main__":
s = Solution()
print(fmt(s.calcEquation([["a", "b"], ["b", "c"]], [2.0, 3.0],
[["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]])))
print(fmt(s.calcEquation([["a", "b"], ["b", "c"], ["bc", "cd"]], [1.5, 2.5, 5.0],
[["a", "c"], ["c", "b"], ["bc", "cd"], ["cd", "bc"]])))
print(fmt(s.calcEquation([["a", "b"]], [0.5],
[["a", "b"], ["b", "a"], ["a", "c"], ["x", "y"]])))RecapThe whole problem in a few lines, for the night before
- Spot it: equations like a / b = 2.0, then queries like a / c that need a chain of them
- Idea: build a graph where a to b has weight v and b to a has weight 1/v; for each query, DFS or BFS from the numerator to the denominator and multiply the weights on the path
- Cost: O(Q x (V + E)) time, O(V + E) space
- Trap: an unknown variable or no path gives -1.0, and x / x is 1.0 only if x appears in the equations
Interview follow-ups
New equations keep arriving between queries. Which approach fits better?
Weighted union-find. Each new equation is one union in near O(1), and each query is two finds in near O(1). The BFS approach would have to search again for every query. Removing an equation, though, is hard for union-find, so if equations can also be deleted, keep the graph and use BFS.
The input might contain a contradiction (like
a / b = 2andb / a = 3). How do you detect it?With union-find, when an equation's two variables are already in the same group, compute their ratio from the stored weights and compare it with the given value. If they differ by more than a small tolerance (say
1e-9), report a contradiction. This catches bad conversion tables before they give silently wrong numbers.Return the chain of conversions used, not just the result.
In the BFS approach, record the parent of each variable when you first reach it. When you reach
d, walk back through the parents tocand reverse the list. That gives something likenode → vCPU → thread, which is useful for showing how a figure in a report was derived.
Frequently asked questions
If a / b = v, then b / a is the same fraction flipped over, which is 1 / v. Adding both directions means any query can be answered by walking the graph either way. Without the reverse link, a query like b / a would find no path and wrongly return -1.
The problem treats a variable that never appears in an equation as undefined, so nothing about it can be determined — not even dividing it by itself. That's why the code checks "is this variable known?" before "are both variables the same?". Swapping those two checks is the most common bug on this problem.
No. The problem promises there are no contradictions, so every path between two variables gives the same product. BFS, DFS or union-find can each find a different route and still get the same answer. Only floating-point rounding might differ in the last digits, which the 5-decimal answer hides.
Yes. Floyd-Warshall-style precomputation fills in ratio[i][j] for every pair of variables: for each middle variable k, if i / k and k / j are known, set i / j to their product. That setup costs O(V³), then every query is a table lookup. With 40 variables that's 64,000 steps — fine here, but it grows fast.
It is unit and rate conversion with only partial information: instance sizes to vCPUs, vCPUs to threads, one cloud's pricing units to another's, or currency rates for a cost report. Knowing when you can't convert (a unit you've never seen, or two unconnected groups) matters as much as the conversion itself.