You are given direct ownership relationships between companies. Each relationship states that one company owns a percentage of another company.

Find the total percentage of targetCompany owned by ownerCompany, including both direct and indirect ownership.

Class

CompanyOwnershipAnalyzer

Method

getOwnershipPercentage

public double getOwnershipPercentage(List<String> ownerships, String ownerCompany, String targetCompany)

• ownerships contains the direct ownership relationships.
• ownerCompany is the company whose ownership is being calculated.
• targetCompany is the company being owned.
• Returns the total percentage of targetCompany owned by ownerCompany.

Ownership Format

Every relationship uses the format "ownerCompany,ownedCompany,percentage".

• ownerCompany directly owns percentage percent of ownedCompany.
• For example, "atlas,beacon,40" means that atlas directly owns 40% of beacon.

Ownership Rules

• A company owns 100% of itself.
• A direct relationship contributes its stated percentage.
• For an indirect ownership path, multiply the ownership percentages along that path.
• If a path contains percentages p1, p2, ..., pk, its contribution is 100 * (p1 / 100) * (p2 / 100) * ... * (pk / 100).
• Add the contributions from every direct and indirect path from ownerCompany to targetCompany.
• Return 0.0 when no ownership path exists.
• The ownership relationships never contain a cycle.
• The supplied ownerships list must not be modified.

Constraints

• 1 ≤ ownerships.size() ≤ 100,000
• Every relationship contains exactly three comma-separated values without spaces.
• 1 ≤ companyId.length() ≤ 20
• Every company identifier contains only lowercase English letters.
• 0 < percentage ≤ 100
• Every percentage is a valid decimal number with at most four digits after the decimal point.
• Each ordered pair of companies appears in at most one direct ownership relationship.
• A company never directly owns itself.
• The sum of the direct ownership percentages of any company does not exceed 100.
• ownerCompany and targetCompany appear in the supplied relationships.
• The ownership graph is directed and acyclic.
• The returned value is accepted when its absolute error is at most 0.000000001.
• ownerships, its elements, ownerCompany, and targetCompany are never null.

Examples

Example 1

getOwnershipPercentage( ownerships = List.of("atlas,beacon,40", "beacon,delta,50", "atlas,cobalt,25", "cobalt,delta,20", "atlas,delta,10"), ownerCompany = "atlas", targetCompany = "delta")

Output: 35.0

The direct ownership is 10%. The paths through beacon and cobalt contribute 40% * 50% = 20% and 25% * 20% = 5%. The total is 35%.

Example 2

getOwnershipPercentage( ownerships = List.of("atlas,beacon,40", "beacon,delta,50", "atlas,cobalt,25", "cobalt,delta,20", "atlas,delta,10"), ownerCompany = "delta", targetCompany = "atlas")

Output: 0.0

There is no ownership path from delta to atlas.

Example 3

getOwnershipPercentage( ownerships = List.of("atlas,beacon,40", "beacon,delta,50"), ownerCompany = "beacon", targetCompany = "beacon")

Output: 100.0

A company owns 100% of itself.