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.

This problem is based on graphs , weights and strings:

  • Map the strings to ids and create a disjoint set
  • weights should be maintained for each pair of strings
    I have used disjoint sets approach here.

Creating a disjoint set for strings:
This problem is designed with the strings. Disjoint sets use a root array and connected elements will point one element. For more info on disjoint sets please go through graphs section in explore area.
In C language if we need to use disjoint set for strings, we should give an id for each string. So using an array of char * pointers strs and num_strs to save strings pointers and map each string to one id (starts from 0). Basically mapping the strings to ids.
While going through equations, if it is a new string, we specify the an id else returned mapped id.
Once strings are mapped to ids, disjoint sets can be created using find and union functions.

Weights:
Main issue which we need to understand here is how to maintain weights (values[]) and how to calculate them. I have used 2D array to maintain these weights and initialised to 1s. If (s1, s2, w1) is given, get the mapped s1 and s2 ids and set wt[s1][s2] to w1 and wt[s2][s1] to 1/w1 .
When we do union of (s1, s2) , we update root, rnk and wt arrays. While linking x, y through rx and ry , weights should be caluculated for wt[rx][ry] as wt[rx][ry] = wt[rx][x] wt[y][ry] wt[x][y];

Queries:
These queries consists of pair of strings. These strings may or may not exist in disjoint set. If not there in map set, just set the result as -1 and go for the next pair.
If both the strings are matching with the map set, check if there is calculated weight value, else get the root values for these string mapped ids and calculate the weight.

Tried another approach of converting string to numbers and then do mapping:

--

--

www.linkedin.com/in/jyothivs

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store