We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check for Contradictions in Equations

Number: 2065

Difficulty: Hard

Paid? Yes

Companies: Amazon, Uber

Problem Description

Given a set of equations of the form A / B = k, where each equation relates two variables with a real number, determine if there is any contradiction among the equations. A contradiction occurs if the value computed for an equation via other relationships differs from the provided ratio beyond a tolerance (absolute difference < 10^-5).

Key Insights

  • Model the problem as a graph where each variable is a node.
  • Each equation creates an edge connecting two nodes with an associated weight.
  • Use Depth-First Search (DFS) to propagate and assign a relative value (ratio) to each variable in a connected component.
  • During DFS, if a variable is revisited, compare the computed ratio with the stored ratio to check for consistency.
  • A difference greater than 10^-5 between the computed and stored ratios indicates a contradiction.

Space and Time Complexity

Time Complexity: O(N + M), where N is the number of variables (nodes) and M is the number of equations (edges), since each node and edge is processed during DFS. Space Complexity: O(N + M), for storing the graph and recursion stack (or Union-Find structures).

Solution

We solve the problem by constructing an adjacency list to represent the graph, where each node (variable) connects with others by storing the corresponding division factors. We then use DFS to assign each variable a relative value (or ratio) starting from an arbitrary value of 1 for each connected component. As we propagate these ratios, if we revisit a node and the current computed ratio deviates from its stored value beyond a tolerance (10^-5), we have detected a contradiction. This method ensures that any inconsistency among provided equations is identified.

Code Solutions

# Python solution using DFS.
def checkContradictions(equations, values):
    from collections import defaultdict
    graph = defaultdict(list)
    
    # Build graph: each equation A / B = value leads to two directed edges.
    for (var1, var2), value in zip(equations, values):
        graph[var1].append((var2, value))
        graph[var2].append((var1, 1.0 / value))
    
    # Store computed ratio relative to component's starting variable.
    ratios = {}
    
    def dfs(var, curr_ratio):
        if var in ratios:
            return abs(ratios[var] - curr_ratio) < 1e-5
        ratios[var] = curr_ratio
        for neighbor, value in graph[var]:
            if not dfs(neighbor, curr_ratio * value):
                return False
        return True
    
    # Run DFS for all unvisited variables.
    for variable in graph:
        if variable not in ratios:
            if not dfs(variable, 1.0):
                return True  # Contradiction found
    return False  # No contradiction

# Example usages:
print(checkContradictions([["a", "b"], ["b", "c"], ["a", "c"]], [3, 0.5, 1.5]))  # Expected output: False
print(checkContradictions([["le", "et"], ["le", "code"], ["code", "et"]], [2, 5, 0.5]))  # Expected output: True
← Back to All Questions