#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/union-find/problem-evaluate-division

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/union-find/problem-evaluate-division

Repovive

Problem - Evaluate Division - Union-Find | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Problem - Evaluate Division

Division as graph traversal

Given equations like $a/b = 2.0$ and $b/c = 3.0$ , answer queries like $a/c = ?$ and $a/a = ?$ .

Return $-1.0$ for undefined queries (variables not in equations or not connected).

Example:

equations = [["a","b"],["b","c"]]
values = [2.0, 3.0]
queries = [["a","c"],["b","a"],["a","e"]]
Output: [6.0, 0.5, -1.0]

$a/c = (a/b) \cdot (b/c) = 2 \cdot 3 = 6$

You're implementing weighted Union-Find: edge weights are division ratios.

Constraints: up to 20 equations and 20 queries.