New update is available. Click here to update.

Last Updated: 9 Jan, 2021

Difficulty: Moderate

```
'EQUATIONS' = { {“a”, ”s”} , {“s”, “r”} }
'VALUES' = { 1.5, 2 }
queries = { {“a”, “r” } }
For the above example (a / s) = 1.5 and (s / r) = 2 therefore (a / r) = 1.5 * 2 = 3.
```

```
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.
The first line of each test case contains two integers, ‘N’ and ‘Q,’ separated by a single space denoting the number of the equations and the number of queries, respectively.
The second line of each test case contains ‘N’ strings denoting the numerator variable of the 'EQUATIONS'.
The third line of each test case contains ‘N’ strings denoting the denominator variable of the 'EQUATIONS'.
The fourth line of each test case contains ‘N’ real numbers denoting the 'VALUE' of each fraction.
The fifth line of each test case contains ‘Q’ strings denoting the numerator variable for each query.
The sixth line of each test case contains ‘Q’ strings denoting the denominator variable for each query.
```

```
For each test case, return the value of the fraction up to 5 decimal places or -1 if the value of the fraction cannot be determined. All values are separated by a single space.
Your output will be considered correct if the relative error does not exceed 10^(-6).
```

```
You don’t need to print anything, It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 50
1 <= N <= 100
1 <= Q <= 100
1 <= |S| <= 10
0.0 < values[i] <= 100.0
Where '|S|' denotes the length of the variables, and 'VALUES[i]' denotes the value of the i’th equation.
Time limit: 1 sec
```

The idea is to construct a weighted directed graph from the given equations. For each given equation, let’s make an edge from the numerator variable to the denominator variable with weight equal to the value of the equation and another edge from the denominator to the numerator with weight equal to the inverse of the value of the equation. After making the graph to solve any query, we will need to find a path from the numerator to the denominator.

Let’s consider any two nodes in the graph ‘A’ and ‘B, then the path from ‘A’ to ‘B’ will denote the fraction ‘A' / ‘B’, and its value will be equal to the multiplication of the weights of all edges on the path from ‘A’ to ‘B’.

Let’s consider the following path from ‘A’ to ‘B’ (A -> X -> Y -> B); we know that each directed of the form P->Q represents a fraction P/Q. Hence the value of this path will be (A / X) * (X / Y) * (Y / B) = A / B.

The steps are as follows :

- Iterate through the ‘EQUATIONS’ array; let’s say we are currently at index ‘i’.
- Insert an edge from the numerator variable to the denominator variable with weight equal to ‘VALUES[i]’.
- Also, insert an edge from the denominator variable to the numerator variable with a weight equal to 1 / ‘VALUES[i]’.

- Iterate through the queries; let’s say the numerator and denominator for the current query are ‘NUM' and ’DEN'.
- Traverse the graph to find a path from ‘NUM' and ‘DEN’ using Depth First Search Algorithm.
- If there is no such path, then the value cannot be determined. Hence the result for this query will be -1.
- Otherwise, the answer for this query will be the product of all values on the path from ‘NUM' to ‘DEN’.

This approach is the same as the previous approach, but in this approach, we will use the breadth-first search algorithm for traversing the graph for each query.

Let’s consider any two nodes in the graph ‘A’ and ‘B’, then the path from ‘A’ to ‘B’ will denote the fraction A/B, and it’s value will be equal to multiplication of the weights of all edges on the path from ‘A’ to ‘B’.

Let’s consider the following path from ‘A’ to ‘B’ (A -> X -> Y -> Z); we know that each directed of the form P -> Q represents a fraction P/Q; hence the value of this path will be (A / X) * (X / Y) * (Y / Z) = A / Z.

The steps are as follows :

- Iterate through the ‘EQUATIONS’ array; let’s say we are currently at index ‘i’.
- Insert an edge from the numerator variable to the denominator variable with weight equal to ‘VALUES[i]'.
- Also, insert an edge from the denominator variable to the numerator variable with a weight equal to 1 / ‘VALUES[i]’.

- Iterate through the queries; let’s say the numerator and denominator for the current query are ‘NUM' and ‘DEN’.
- Traverse the graph to find a path from ‘NUM' and ‘DEN’ using the Breadth-First Search Algorithm.
- If there is no such path, then the value cannot be determined. Hence the result for this query will be -1.
- Otherwise, the answer for this query will be the product of all values on the path from ‘NUM' to ‘DEN’.

In this approach, like the previous approach, we create a directed weighted graph for any equation** X/Y = C**,** Y** is the parent of** X,** and the distance from** Y** to **X** is **C**. Each time we move a node up in the graph to get the result of the equation we multiply the path length

For example:

Given **X / Y=C **and **Y/ Z =B**, The graph would be like **Z - > Y -> X.** To get the result of **X / Z**, we start with **1** and multiply it by the path weight of **Y -> X** and **Z -> Y**

- Then for every equation given, we union the nodes, update each node’s root and add the distance of each node to its root.
- For each query, if the
**A/B**if the roots of**A**and**B**are equal, then it’s possible to find the equation**A/B**that is the**distance(A)/distance(B);**otherwise, it is not possible**-1**is the answer.

Each time we find a parent of a node we update its distance also, **distance(node) = distance(node)*distance(parent)**

We create a function **getRoot(roots, distances, node)** to find a node’s distance from its root. Here the **roots** are the map of all nodes and their **roots**. The **distances **is the map of distances or factors of each node from its root. The **node** is the current node.

Algorithm:

- In the
**getRoot(roots, distances, node)**- If the
**node**is not is**roots**- Set
**roots[node]**as**node** - Set
**distances[node]**as**1** - Return
**node**

- Set
- If
**roots[node]**is equal to the**node**- Return
**node**

- Return
- Set
**parent**as**roots[node]** - Set
**parentRoot**as**getRoot(roots, distances, parent)** - Set
**roots[node]**as**parentRoot** - Set
**distances[node]**as**distance[node] * distance[parent]** - Return
**parentRoot**

- If the

- Initialise two empty hashmaps
**distances**and**roots** - Iterate
**i**from**0**to size of**equations -1**- Set
**equation**as**equations[i]** - Set
**root1**as**getRoot(roots, distances, equation[0])** - Set
**root2**as**getRoot(roots, distances, equation[1])** - Set
**roots[root1]**as**root2** - Set
**distances[root1]**as**distances[equation[1]] * values[i] / distances[eqaution[0]]**

- Set
- Initialise an empty array
**results** - Iterate query through queries
- If
**query[0]**is not**roots**or**query[1]**is not in**roots**, then- Insert
**-1**in**results** **Continue**the loop- Set
**root1**as**getRoot(roots, distances, query[0])**

- Insert
- Set
**root2**as**getRoot(roots, distances, query[1])** - If
**root1**is not equal to**root2**- Insert
**-1**into**results** **Continue**the loop

- Insert
- Insert
**distances[query[0]] / distances[query[1]]**in the**results**array

- If
- Finally return
**results**

SIMILAR PROBLEMS

COUNT ISLANDS

Posted: 14 Sep, 2022

Difficulty: Moderate

Capturing Grid

Posted: 14 Sep, 2022

Difficulty: Moderate

The Summit

Posted: 15 Sep, 2022

Difficulty: Easy

Rotting Oranges

Posted: 15 Sep, 2022

Difficulty: Moderate

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Popular Interview Problems: