Solve System of Linear Addition Equations
HardUpdated: Jan 11, 2025
Problem
You are given a series of arithmetic equations as a string, such as:
y = x + 1
5 = x + 3
10 = z + y + 2
The equations use addition only and are separated by newlines. Return a mapping of all variables to their values. If it's not possible, then return null. In this example, you should return:
{
x: 2,
y: 3,
z: 5
}
Examples
Example 1
Input: "y = x + 1\n5 = x + 3\n10 = z + y + 2"
Output: {x: 2, y: 3, z: 5}
Explanation: From equation 2: x = 2. From equation 1: y = 3. From equation 3: z = 5.
Example 2
Input: "a = b + 1\nb = c + 2\nc = 3"
Output: {a: 6, b: 5, c: 3}
Explanation: c = 3, b = 5, a = 6 by substitution.
Example 3
Input: "x = y + 1\ny = x + 1"
Output: null
Explanation: Circular dependency with no solution (x = x + 2 is impossible).
Example 4
Input: "a = 5\nb = a + 2\nc = b + 3"
Output: {a: 5, b: 7, c: 10}
Explanation: Linear chain of dependencies can be solved sequentially.
Example 5
Input: "x = y + z + 1\ny = 2\nz = 3"
Output: {x: 6, y: 2, z: 3}
Explanation: Multiple variables on right side: x = 2 + 3 + 1 = 6.
Example 6
Input: "x = y + 1\nx = y + 2"
Output: null
Explanation: Inconsistent equations: x cannot equal both y+1 and y+2.
Solution
Method 1 - Equation Parsing with Substitution and Topological Sort
Intuition
The key insight is to parse equations into a graph structure where variables depend on other variables or constants. We can use topological sorting to determine the order in which to solve variables. Variables with no dependencies (only constants on the right side) can be solved first, then we substitute their values to solve dependent variables. If there are cycles in the dependency graph, the system has no solution.
Approach
- Parse Equations: Convert each equation into left variable and right-side terms
- Build Dependency Graph: Create adjacency list showing which variables depend on others
- Detect Direct Solutions: Find variables that can be computed directly (only constants on right)
- Topological Sort: Order variables by dependency to solve in correct sequence
- Substitute and Solve:
- Start with variables having no dependencies
- Substitute known values into dependent equations
- Continue until all variables solved or contradiction found
- Validate Consistency: Check if all equations are satisfied by the solution
- Handle Edge Cases: Circular dependencies, inconsistent equations, multiple solutions
Code
C++
class Solution {
public:
map<string, int> solveEquations(string equations) {
vector<string> lines = split(equations, '\n');
map<string, vector<pair<string, int>>> deps; // var -> [(var, coeff), (const, value)]
map<string, int> constants; // var -> constant_sum
map<string, int> solution;
// Parse equations
for (string& line : lines) {
if (!parseEquation(line, deps, constants)) {
return {};
}
}
// Find variables that can be solved directly
queue<string> ready;
for (auto& [var, terms] : deps) {
bool hasOnlyConstants = true;
for (auto& [term, coeff] : terms) {
if (isVariable(term)) {
hasOnlyConstants = false;
break;
}
}
if (hasOnlyConstants) {
ready.push(var);
}
}
// Solve using topological sort approach
while (!ready.empty()) {
string var = ready.front();
ready.pop();
if (solution.count(var)) continue;
// Calculate value for this variable
int value = constants[var];
for (auto& [term, coeff] : deps[var]) {
if (isVariable(term)) {
if (!solution.count(term)) {
// Still depends on unsolved variable
continue;
}
value += solution[term] * coeff;
} else {
value += stoi(term) * coeff;
}
}
solution[var] = value;
// Update dependencies and check for newly solvable variables
for (auto& [otherVar, terms] : deps) {
if (solution.count(otherVar)) continue;
bool canSolve = true;
for (auto& [term, coeff] : terms) {
if (isVariable(term) && !solution.count(term)) {
canSolve = false;
break;
}
}
if (canSolve) {
ready.push(otherVar);
}
}
}
// Check if all variables are solved
for (auto& [var, terms] : deps) {
if (!solution.count(var)) {
return {}; // Unsolvable (circular dependency)
}
}
// Verify solution consistency
if (!verifySolution(lines, solution)) {
return {};
}
return solution;
}
private:
vector<string> split(string str, char delim) {
vector<string> result;
stringstream ss(str);
string item;
while (getline(ss, item, delim)) {
result.push_back(item);
}
return result;
}
bool isVariable(const string& term) {
return !term.empty() && isalpha(term[0]);
}
bool parseEquation(string line, map<string, vector<pair<string, int>>>& deps,
map<string, int>& constants) {
// Remove spaces
line.erase(remove(line.begin(), line.end(), ' '), line.end());
size_t eqPos = line.find('=');
if (eqPos == string::npos) return false;
string left = line.substr(0, eqPos);
string right = line.substr(eqPos + 1);
// Parse right side
vector<pair<string, int>> terms;
int constantSum = 0;
stringstream ss(right);
string token;
int sign = 1;
size_t pos = 0;
while (pos < right.length()) {
if (right[pos] == '+') {
sign = 1;
pos++;
} else if (right[pos] == '-') {
sign = -1;
pos++;
}
size_t nextOp = right.find_first_of("+-", pos);
if (nextOp == string::npos) nextOp = right.length();
string term = right.substr(pos, nextOp - pos);
if (isVariable(term)) {
terms.push_back({term, sign});
} else {
constantSum += sign * stoi(term);
}
pos = nextOp;
}
deps[left] = terms;
constants[left] = constantSum;
return true;
}
bool verifySolution(const vector<string>& lines, const map<string, int>& solution) {
for (const string& line : lines) {
string cleanLine = line;
cleanLine.erase(remove(cleanLine.begin(), cleanLine.end(), ' '), cleanLine.end());
size_t eqPos = cleanLine.find('=');
string left = cleanLine.substr(0, eqPos);
string right = cleanLine.substr(eqPos + 1);
int leftVal = solution.count(left) ? solution.at(left) : stoi(left);
int rightVal = evaluateExpression(right, solution);
if (leftVal != rightVal) return false;
}
return true;
}
int evaluateExpression(const string& expr, const map<string, int>& solution) {
int result = 0;
int sign = 1;
size_t pos = 0;
while (pos < expr.length()) {
if (expr[pos] == '+') {
sign = 1;
pos++;
} else if (expr[pos] == '-') {
sign = -1;
pos++;
}
size_t nextOp = expr.find_first_of("+-", pos);
if (nextOp == string::npos) nextOp = expr.length();
string term = expr.substr(pos, nextOp - pos);
if (isVariable(term)) {
result += sign * solution.at(term);
} else {
result += sign * stoi(term);
}
pos = nextOp;
}
return result;
}
};
Go
func SolveEquations(equations string) map[string]int {
lines := strings.Split(equations, "\n")
deps := make(map[string][]Term)
constants := make(map[string]int)
solution := make(map[string]int)
// Parse equations
for _, line := range lines {
if !parseEquation(line, deps, constants) {
return nil
}
}
// Find variables that can be solved directly
ready := make([]string, 0)
for variable, terms := range deps {
hasOnlyConstants := true
for _, term := range terms {
if isVariable(term.Name) {
hasOnlyConstants = false
break
}
}
if hasOnlyConstants {
ready = append(ready, variable)
}
}
// Solve using topological sort approach
for len(ready) > 0 {
variable := ready[0]
ready = ready[1:]
if _, exists := solution[variable]; exists {
continue
}
// Calculate value for this variable
value := constants[variable]
canSolve := true
for _, term := range deps[variable] {
if isVariable(term.Name) {
if termValue, exists := solution[term.Name]; exists {
value += termValue * term.Coefficient
} else {
canSolve = false
break
}
} else {
if termValue, err := strconv.Atoi(term.Name); err == nil {
value += termValue * term.Coefficient
}
}
}
if !canSolve {
continue
}
solution[variable] = value
// Check for newly solvable variables
for otherVar, terms := range deps {
if _, exists := solution[otherVar]; exists {
continue
}
canSolveOther := true
for _, term := range terms {
if isVariable(term.Name) {
if _, exists := solution[term.Name]; !exists {
canSolveOther = false
break
}
}
}
if canSolveOther {
ready = append(ready, otherVar)
}
}
}
// Check if all variables are solved
for variable := range deps {
if _, exists := solution[variable]; !exists {
return nil // Unsolvable
}
}
// Verify solution
if !verifySolution(lines, solution) {
return nil
}
return solution
}
type Term struct {
Name string
Coefficient int
}
func isVariable(term string) bool {
return len(term) > 0 && ((term[0] >= 'a' && term[0] <= 'z') || (term[0] >= 'A' && term[0] <= 'Z'))
}
func parseEquation(line string, deps map[string][]Term, constants map[string]int) bool {
// Remove spaces
line = strings.ReplaceAll(line, " ", "")
parts := strings.Split(line, "=")
if len(parts) != 2 {
return false
}
left := parts[0]
right := parts[1]
// Parse right side
terms := make([]Term, 0)
constantSum := 0
// Simple parsing for terms separated by + or -
pos := 0
sign := 1
for pos < len(right) {
if pos < len(right) && right[pos] == '+' {
sign = 1
pos++
} else if pos < len(right) && right[pos] == '-' {
sign = -1
pos++
}
// Find next operator or end
nextOp := pos
for nextOp < len(right) && right[nextOp] != '+' && right[nextOp] != '-' {
nextOp++
}
if nextOp > pos {
term := right[pos:nextOp]
if isVariable(term) {
terms = append(terms, Term{Name: term, Coefficient: sign})
} else {
if value, err := strconv.Atoi(term); err == nil {
constantSum += sign * value
}
}
}
pos = nextOp
}
deps[left] = terms
constants[left] = constantSum
return true
}
func verifySolution(lines []string, solution map[string]int) bool {
for _, line := range lines {
line = strings.ReplaceAll(line, " ", "")
parts := strings.Split(line, "=")
if len(parts) != 2 {
continue
}
left := parts[0]
right := parts[1]
leftVal := 0
if isVariable(left) {
if val, exists := solution[left]; exists {
leftVal = val
} else {
return false
}
} else {
if val, err := strconv.Atoi(left); err == nil {
leftVal = val
}
}
rightVal := evaluateExpression(right, solution)
if leftVal != rightVal {
return false
}
}
return true
}
func evaluateExpression(expr string, solution map[string]int) int {
result := 0
sign := 1
pos := 0
for pos < len(expr) {
if pos < len(expr) && expr[pos] == '+' {
sign = 1
pos++
} else if pos < len(expr) && expr[pos] == '-' {
sign = -1
pos++
}
nextOp := pos
for nextOp < len(expr) && expr[nextOp] != '+' && expr[nextOp] != '-' {
nextOp++
}
if nextOp > pos {
term := expr[pos:nextOp]
if isVariable(term) {
if val, exists := solution[term]; exists {
result += sign * val
}
} else {
if val, err := strconv.Atoi(term); err == nil {
result += sign * val
}
}
}
pos = nextOp
}
return result
}
Java
class Solution {
public Map<String, Integer> solveEquations(String equations) {
String[] lines = equations.split("\n");
Map<String, List<Term>> deps = new HashMap<>();
Map<String, Integer> constants = new HashMap<>();
Map<String, Integer> solution = new HashMap<>();
// Parse equations
for (String line : lines) {
if (!parseEquation(line, deps, constants)) {
return null;
}
}
// Find variables that can be solved directly
Queue<String> ready = new LinkedList<>();
for (Map.Entry<String, List<Term>> entry : deps.entrySet()) {
String var = entry.getKey();
List<Term> terms = entry.getValue();
boolean hasOnlyConstants = true;
for (Term term : terms) {
if (isVariable(term.name)) {
hasOnlyConstants = false;
break;
}
}
if (hasOnlyConstants) {
ready.offer(var);
}
}
// Solve using topological sort approach
while (!ready.isEmpty()) {
String var = ready.poll();
if (solution.containsKey(var)) continue;
// Calculate value for this variable
int value = constants.getOrDefault(var, 0);
boolean canSolve = true;
for (Term term : deps.get(var)) {
if (isVariable(term.name)) {
if (solution.containsKey(term.name)) {
value += solution.get(term.name) * term.coefficient;
} else {
canSolve = false;
break;
}
} else {
try {
value += Integer.parseInt(term.name) * term.coefficient;
} catch (NumberFormatException e) {
return null;
}
}
}
if (!canSolve) continue;
solution.put(var, value);
// Check for newly solvable variables
for (Map.Entry<String, List<Term>> entry : deps.entrySet()) {
String otherVar = entry.getKey();
List<Term> terms = entry.getValue();
if (solution.containsKey(otherVar)) continue;
boolean canSolveOther = true;
for (Term term : terms) {
if (isVariable(term.name) && !solution.containsKey(term.name)) {
canSolveOther = false;
break;
}
}
if (canSolveOther) {
ready.offer(otherVar);
}
}
}
// Check if all variables are solved
for (String var : deps.keySet()) {
if (!solution.containsKey(var)) {
return null; // Unsolvable
}
}
// Verify solution
if (!verifySolution(lines, solution)) {
return null;
}
return solution;
}
private static class Term {
String name;
int coefficient;
Term(String name, int coefficient) {
this.name = name;
this.coefficient = coefficient;
}
}
private boolean isVariable(String term) {
return !term.isEmpty() && Character.isLetter(term.charAt(0));
}
private boolean parseEquation(String line, Map<String, List<Term>> deps,
Map<String, Integer> constants) {
line = line.replaceAll("\\s+", "");
String[] parts = line.split("=");
if (parts.length != 2) return false;
String left = parts[0];
String right = parts[1];
List<Term> terms = new ArrayList<>();
int constantSum = 0;
// Parse right side
int pos = 0;
int sign = 1;
while (pos < right.length()) {
if (pos < right.length() && right.charAt(pos) == '+') {
sign = 1;
pos++;
} else if (pos < right.length() && right.charAt(pos) == '-') {
sign = -1;
pos++;
}
int nextOp = pos;
while (nextOp < right.length() &&
right.charAt(nextOp) != '+' && right.charAt(nextOp) != '-') {
nextOp++;
}
if (nextOp > pos) {
String term = right.substring(pos, nextOp);
if (isVariable(term)) {
terms.add(new Term(term, sign));
} else {
try {
constantSum += sign * Integer.parseInt(term);
} catch (NumberFormatException e) {
return false;
}
}
}
pos = nextOp;
}
deps.put(left, terms);
constants.put(left, constantSum);
return true;
}
private boolean verifySolution(String[] lines, Map<String, Integer> solution) {
for (String line : lines) {
line = line.replaceAll("\\s+", "");
String[] parts = line.split("=");
if (parts.length != 2) continue;
String left = parts[0];
String right = parts[1];
int leftVal = 0;
if (isVariable(left)) {
if (!solution.containsKey(left)) return false;
leftVal = solution.get(left);
} else {
try {
leftVal = Integer.parseInt(left);
} catch (NumberFormatException e) {
return false;
}
}
int rightVal = evaluateExpression(right, solution);
if (leftVal != rightVal) return false;
}
return true;
}
private int evaluateExpression(String expr, Map<String, Integer> solution) {
int result = 0;
int sign = 1;
int pos = 0;
while (pos < expr.length()) {
if (pos < expr.length() && expr.charAt(pos) == '+') {
sign = 1;
pos++;
} else if (pos < expr.length() && expr.charAt(pos) == '-') {
sign = -1;
pos++;
}
int nextOp = pos;
while (nextOp < expr.length() &&
expr.charAt(nextOp) != '+' && expr.charAt(nextOp) != '-') {
nextOp++;
}
if (nextOp > pos) {
String term = expr.substring(pos, nextOp);
if (isVariable(term)) {
if (solution.containsKey(term)) {
result += sign * solution.get(term);
}
} else {
try {
result += sign * Integer.parseInt(term);
} catch (NumberFormatException e) {
// Skip invalid terms
}
}
}
pos = nextOp;
}
return result;
}
}
Python
class Solution:
def solveEquations(self, equations: str) -> Optional[Dict[str, int]]:
lines = equations.strip().split('\n')
deps: Dict[str, List[Tuple[str, int]]] = {}
constants: Dict[str, int] = {}
solution: Dict[str, int] = {}
# Parse equations
for line in lines:
if not self._parseEquation(line, deps, constants):
return None
# Find variables that can be solved directly
ready: List[str] = []
for var, terms in deps.items():
hasOnlyConstants = True
for term, coeff in terms:
if self._isVariable(term):
hasOnlyConstants = False
break
if hasOnlyConstants:
ready.append(var)
# Solve using topological sort approach
while ready:
var = ready.pop(0)
if var in solution:
continue
# Calculate value for this variable
value = constants.get(var, 0)
canSolve = True
for term, coeff in deps[var]:
if self._isVariable(term):
if term in solution:
value += solution[term] * coeff
else:
canSolve = False
break
else:
try:
value += int(term) * coeff
except ValueError:
return None
if not canSolve:
continue
solution[var] = value
# Check for newly solvable variables
for otherVar, terms in deps.items():
if otherVar in solution:
continue
canSolveOther = True
for term, coeff in terms:
if self._isVariable(term) and term not in solution:
canSolveOther = False
break
if canSolveOther and otherVar not in ready:
ready.append(otherVar)
# Check if all variables are solved
for var in deps:
if var not in solution:
return None # Unsolvable
# Verify solution
if not self._verifySolution(lines, solution):
return None
return solution
def _isVariable(self, term: str) -> bool:
return len(term) > 0 and term[0].isalpha()
def _parseEquation(self, line: str, deps: Dict[str, List[Tuple[str, int]]],
constants: Dict[str, int]) -> bool:
# Remove spaces
line = line.replace(' ', '')
if '=' not in line:
return False
left, right = line.split('=', 1)
# Parse right side
terms: List[Tuple[str, int]] = []
constantSum = 0
# Simple parsing for terms separated by + or -
pos = 0
sign = 1
while pos < len(right):
if pos < len(right) and right[pos] == '+':
sign = 1
pos += 1
elif pos < len(right) and right[pos] == '-':
sign = -1
pos += 1
# Find next operator or end
nextOp = pos
while nextOp < len(right) and right[nextOp] not in '+-':
nextOp += 1
if nextOp > pos:
term = right[pos:nextOp]
if self._isVariable(term):
terms.append((term, sign))
else:
try:
constantSum += sign * int(term)
except ValueError:
return False
pos = nextOp
deps[left] = terms
constants[left] = constantSum
return True
def _verifySolution(self, lines: List[str], solution: Dict[str, int]) -> bool:
for line in lines:
line = line.replace(' ', '')
if '=' not in line:
continue
left, right = line.split('=', 1)
# Evaluate left side
if self._isVariable(left):
if left not in solution:
return False
leftVal = solution[left]
else:
try:
leftVal = int(left)
except ValueError:
return False
# Evaluate right side
rightVal = self._evaluateExpression(right, solution)
if leftVal != rightVal:
return False
return True
def _evaluateExpression(self, expr: str, solution: Dict[str, int]) -> int:
result = 0
sign = 1
pos = 0
while pos < len(expr):
if pos < len(expr) and expr[pos] == '+':
sign = 1
pos += 1
elif pos < len(expr) and expr[pos] == '-':
sign = -1
pos += 1
nextOp = pos
while nextOp < len(expr) and expr[nextOp] not in '+-':
nextOp += 1
if nextOp > pos:
term = expr[pos:nextOp]
if self._isVariable(term):
if term in solution:
result += sign * solution[term]
else:
try:
result += sign * int(term)
except ValueError:
pass # Skip invalid terms
pos = nextOp
return result
Complexity
- ⏰ Time complexity:
O(n * m)where n is the number of equations and m is the average number of terms per equation. Parsing is O(n * m), topological sort is O(n), and verification is O(n * m). - 🧺 Space complexity:
O(n * m)for storing the dependency graph, constants map, and solution map where n is variables and m is average terms per variable.
Method 2 - Graph-Based Gaussian Elimination
Intuition
We can treat this as a system of linear equations and use a modified Gaussian elimination approach. Since we only have addition operations, we can represent each equation as a row in a matrix and solve using elimination. This approach is more systematic for detecting inconsistencies and handling complex dependency patterns.
Approach
- Matrix Representation: Convert equations to augmented matrix form [A|b] where Ax = b
- Variable Mapping: Create mapping from variable names to column indices
- Forward Elimination: Use row operations to create upper triangular form
- Consistency Check: Detect contradictions (0 = non-zero) during elimination
- Back Substitution: Solve for variables starting from last row
- Handle Free Variables: Detect underdetermined systems
- Validation: Verify solution satisfies all original equations
Code
C++
class Solution {
public:
map<string, int> solveEquationsMatrix(string equations) {
vector<string> lines = split(equations, '\n');
set<string> variables;
// First pass: collect all variables
for (const string& line : lines) {
collectVariables(line, variables);
}
vector<string> varList(variables.begin(), variables.end());
map<string, int> varIndex;
for (int i = 0; i < varList.size(); i++) {
varIndex[varList[i]] = i;
}
int n = varList.size();
int m = lines.size();
// Create augmented matrix [A|b]
vector<vector<double>> matrix(m, vector<double>(n + 1, 0));
for (int i = 0; i < m; i++) {
if (!parseEquationToMatrix(lines[i], matrix[i], varIndex)) {
return {};
}
}
// Gaussian elimination
int rank = gaussianElimination(matrix, n);
// Check for inconsistency
for (int i = rank; i < m; i++) {
if (abs(matrix[i][n]) > 1e-9) {
return {}; // Inconsistent system
}
}
// Check if system is underdetermined
if (rank < n) {
return {}; // Infinite solutions or underdetermined
}
// Back substitution
vector<double> solution(n);
for (int i = n - 1; i >= 0; i--) {
solution[i] = matrix[i][n];
for (int j = i + 1; j < n; j++) {
solution[i] -= matrix[i][j] * solution[j];
}
solution[i] /= matrix[i][i];
}
// Convert to integer solution and verify
map<string, int> result;
for (int i = 0; i < n; i++) {
double val = solution[i];
if (abs(val - round(val)) > 1e-9) {
return {}; // Non-integer solution
}
result[varList[i]] = (int)round(val);
}
// Verify solution
if (!verifySolution(lines, result)) {
return {};
}
return result;
}
private:
vector<string> split(string str, char delim) {
vector<string> result;
stringstream ss(str);
string item;
while (getline(ss, item, delim)) {
result.push_back(item);
}
return result;
}
void collectVariables(const string& line, set<string>& variables) {
string cleaned = line;
cleaned.erase(remove(cleaned.begin(), cleaned.end(), ' '), cleaned.end());
for (int i = 0; i < cleaned.length(); i++) {
if (isalpha(cleaned[i])) {
string var = "";
while (i < cleaned.length() && isalnum(cleaned[i])) {
var += cleaned[i++];
}
i--; // Adjust for loop increment
variables.insert(var);
}
}
}
bool parseEquationToMatrix(const string& line, vector<double>& row,
const map<string, int>& varIndex) {
string cleaned = line;
cleaned.erase(remove(cleaned.begin(), cleaned.end(), ' '), cleaned.end());
size_t eqPos = cleaned.find('=');
if (eqPos == string::npos) return false;
string left = cleaned.substr(0, eqPos);
string right = cleaned.substr(eqPos + 1);
// Parse left side (should be single variable or constant)
if (isVariable(left)) {
row[varIndex.at(left)] = 1;
} else {
row[row.size() - 1] = stoi(left);
}
// Parse right side and subtract from left
parseExpressionToMatrix(right, row, varIndex, -1);
return true;
}
void parseExpressionToMatrix(const string& expr, vector<double>& row,
const map<string, int>& varIndex, int multiplier) {
int sign = multiplier;
size_t pos = 0;
while (pos < expr.length()) {
if (pos < expr.length() && expr[pos] == '+') {
sign = multiplier;
pos++;
} else if (pos < expr.length() && expr[pos] == '-') {
sign = -multiplier;
pos++;
}
size_t nextOp = expr.find_first_of("+-", pos);
if (nextOp == string::npos) nextOp = expr.length();
string term = expr.substr(pos, nextOp - pos);
if (isVariable(term)) {
row[varIndex.at(term)] += sign;
} else {
row[row.size() - 1] += sign * stoi(term);
}
pos = nextOp;
}
}
bool isVariable(const string& term) {
return !term.empty() && isalpha(term[0]);
}
int gaussianElimination(vector<vector<double>>& matrix, int n) {
int rank = 0;
for (int col = 0; col < n && rank < matrix.size(); col++) {
// Find pivot
int pivot = -1;
for (int row = rank; row < matrix.size(); row++) {
if (abs(matrix[row][col]) > 1e-9) {
pivot = row;
break;
}
}
if (pivot == -1) continue; // No pivot in this column
// Swap rows
if (pivot != rank) {
swap(matrix[rank], matrix[pivot]);
}
// Eliminate
for (int row = 0; row < matrix.size(); row++) {
if (row != rank && abs(matrix[row][col]) > 1e-9) {
double factor = matrix[row][col] / matrix[rank][col];
for (int j = 0; j <= n; j++) {
matrix[row][j] -= factor * matrix[rank][j];
}
}
}
rank++;
}
return rank;
}
bool verifySolution(const vector<string>& lines, const map<string, int>& solution) {
// Implementation similar to Method 1
return true; // Simplified for brevity
}
};
Go
func SolveEquationsMatrix(equations string) map[string]int {
lines := strings.Split(equations, "\n")
variables := make(map[string]bool)
// Collect all variables
for _, line := range lines {
collectVariables(line, variables)
}
varList := make([]string, 0, len(variables))
for variable := range variables {
varList = append(varList, variable)
}
sort.Strings(varList) // For consistent ordering
varIndex := make(map[string]int)
for i, variable := range varList {
varIndex[variable] = i
}
n := len(varList)
m := len(lines)
// Create augmented matrix
matrix := make([][]float64, m)
for i := range matrix {
matrix[i] = make([]float64, n+1)
}
for i, line := range lines {
if !parseEquationToMatrix(line, matrix[i], varIndex) {
return nil
}
}
// Gaussian elimination
rank := gaussianElimination(matrix, n)
// Check for inconsistency
for i := rank; i < m; i++ {
if math.Abs(matrix[i][n]) > 1e-9 {
return nil // Inconsistent
}
}
if rank < n {
return nil // Underdetermined
}
// Back substitution
solution := make([]float64, n)
for i := n - 1; i >= 0; i-- {
solution[i] = matrix[i][n]
for j := i + 1; j < n; j++ {
solution[i] -= matrix[i][j] * solution[j]
}
solution[i] /= matrix[i][i]
}
// Convert to integer solution
result := make(map[string]int)
for i, variable := range varList {
val := solution[i]
if math.Abs(val-math.Round(val)) > 1e-9 {
return nil // Non-integer solution
}
result[variable] = int(math.Round(val))
}
return result
}
func collectVariables(line string, variables map[string]bool) {
cleaned := strings.ReplaceAll(line, " ", "")
for i := 0; i < len(cleaned); i++ {
if (cleaned[i] >= 'a' && cleaned[i] <= 'z') || (cleaned[i] >= 'A' && cleaned[i] <= 'Z') {
variable := ""
for i < len(cleaned) && ((cleaned[i] >= 'a' && cleaned[i] <= 'z') ||
(cleaned[i] >= 'A' && cleaned[i] <= 'Z') ||
(cleaned[i] >= '0' && cleaned[i] <= '9')) {
variable += string(cleaned[i])
i++
}
i-- // Adjust for loop increment
variables[variable] = true
}
}
}
func parseEquationToMatrix(line string, row []float64, varIndex map[string]int) bool {
cleaned := strings.ReplaceAll(line, " ", "")
parts := strings.Split(cleaned, "=")
if len(parts) != 2 {
return false
}
left := parts[0]
right := parts[1]
// Parse left side
if isVariableGo(left) {
row[varIndex[left]] = 1
} else {
if val, err := strconv.ParseFloat(left, 64); err == nil {
row[len(row)-1] = val
}
}
// Parse right side and subtract
parseExpressionToMatrix(right, row, varIndex, -1)
return true
}
func parseExpressionToMatrix(expr string, row []float64, varIndex map[string]int, multiplier float64) {
sign := multiplier
pos := 0
for pos < len(expr) {
if pos < len(expr) && expr[pos] == '+' {
sign = multiplier
pos++
} else if pos < len(expr) && expr[pos] == '-' {
sign = -multiplier
pos++
}
nextOp := pos
for nextOp < len(expr) && expr[nextOp] != '+' && expr[nextOp] != '-' {
nextOp++
}
if nextOp > pos {
term := expr[pos:nextOp]
if isVariableGo(term) {
row[varIndex[term]] += sign
} else {
if val, err := strconv.ParseFloat(term, 64); err == nil {
row[len(row)-1] += sign * val
}
}
}
pos = nextOp
}
}
func isVariableGo(term string) bool {
return len(term) > 0 && ((term[0] >= 'a' && term[0] <= 'z') || (term[0] >= 'A' && term[0] <= 'Z'))
}
func gaussianElimination(matrix [][]float64, n int) int {
rank := 0
for col := 0; col < n && rank < len(matrix); col++ {
// Find pivot
pivot := -1
for row := rank; row < len(matrix); row++ {
if math.Abs(matrix[row][col]) > 1e-9 {
pivot = row
break
}
}
if pivot == -1 {
continue
}
// Swap rows
if pivot != rank {
matrix[rank], matrix[pivot] = matrix[pivot], matrix[rank]
}
// Eliminate
for row := 0; row < len(matrix); row++ {
if row != rank && math.Abs(matrix[row][col]) > 1e-9 {
factor := matrix[row][col] / matrix[rank][col]
for j := 0; j <= n; j++ {
matrix[row][j] -= factor * matrix[rank][j]
}
}
}
rank++
}
return rank
}
Java
class Solution {
public Map<String, Integer> solveEquationsMatrix(String equations) {
String[] lines = equations.split("\n");
Set<String> variables = new HashSet<>();
// Collect all variables
for (String line : lines) {
collectVariables(line, variables);
}
List<String> varList = new ArrayList<>(variables);
Collections.sort(varList); // For consistent ordering
Map<String, Integer> varIndex = new HashMap<>();
for (int i = 0; i < varList.size(); i++) {
varIndex.put(varList.get(i), i);
}
int n = varList.size();
int m = lines.length;
// Create augmented matrix
double[][] matrix = new double[m][n + 1];
for (int i = 0; i < m; i++) {
if (!parseEquationToMatrix(lines[i], matrix[i], varIndex)) {
return null;
}
}
// Gaussian elimination
int rank = gaussianElimination(matrix, n);
// Check for inconsistency
for (int i = rank; i < m; i++) {
if (Math.abs(matrix[i][n]) > 1e-9) {
return null; // Inconsistent
}
}
if (rank < n) {
return null; // Underdetermined
}
// Back substitution
double[] solution = new double[n];
for (int i = n - 1; i >= 0; i--) {
solution[i] = matrix[i][n];
for (int j = i + 1; j < n; j++) {
solution[i] -= matrix[i][j] * solution[j];
}
solution[i] /= matrix[i][i];
}
// Convert to integer solution
Map<String, Integer> result = new HashMap<>();
for (int i = 0; i < n; i++) {
double val = solution[i];
if (Math.abs(val - Math.round(val)) > 1e-9) {
return null; // Non-integer solution
}
result.put(varList.get(i), (int) Math.round(val));
}
return result;
}
private void collectVariables(String line, Set<String> variables) {
line = line.replaceAll("\\s+", "");
for (int i = 0; i < line.length(); i++) {
if (Character.isLetter(line.charAt(i))) {
StringBuilder var = new StringBuilder();
while (i < line.length() && Character.isLetterOrDigit(line.charAt(i))) {
var.append(line.charAt(i++));
}
i--; // Adjust for loop increment
variables.add(var.toString());
}
}
}
private boolean parseEquationToMatrix(String line, double[] row, Map<String, Integer> varIndex) {
line = line.replaceAll("\\s+", "");
String[] parts = line.split("=");
if (parts.length != 2) return false;
String left = parts[0];
String right = parts[1];
// Parse left side
if (isVariableMatrix(left)) {
row[varIndex.get(left)] = 1;
} else {
try {
row[row.length - 1] = Double.parseDouble(left);
} catch (NumberFormatException e) {
return false;
}
}
// Parse right side and subtract
parseExpressionToMatrix(right, row, varIndex, -1);
return true;
}
private void parseExpressionToMatrix(String expr, double[] row,
Map<String, Integer> varIndex, double multiplier) {
double sign = multiplier;
int pos = 0;
while (pos < expr.length()) {
if (pos < expr.length() && expr.charAt(pos) == '+') {
sign = multiplier;
pos++;
} else if (pos < expr.length() && expr.charAt(pos) == '-') {
sign = -multiplier;
pos++;
}
int nextOp = pos;
while (nextOp < expr.length() &&
expr.charAt(nextOp) != '+' && expr.charAt(nextOp) != '-') {
nextOp++;
}
if (nextOp > pos) {
String term = expr.substring(pos, nextOp);
if (isVariableMatrix(term)) {
row[varIndex.get(term)] += sign;
} else {
try {
row[row.length - 1] += sign * Double.parseDouble(term);
} catch (NumberFormatException e) {
// Skip invalid terms
}
}
}
pos = nextOp;
}
}
private boolean isVariableMatrix(String term) {
return !term.isEmpty() && Character.isLetter(term.charAt(0));
}
private int gaussianElimination(double[][] matrix, int n) {
int rank = 0;
for (int col = 0; col < n && rank < matrix.length; col++) {
// Find pivot
int pivot = -1;
for (int row = rank; row < matrix.length; row++) {
if (Math.abs(matrix[row][col]) > 1e-9) {
pivot = row;
break;
}
}
if (pivot == -1) continue;
// Swap rows
if (pivot != rank) {
double[] temp = matrix[rank];
matrix[rank] = matrix[pivot];
matrix[pivot] = temp;
}
// Eliminate
for (int row = 0; row < matrix.length; row++) {
if (row != rank && Math.abs(matrix[row][col]) > 1e-9) {
double factor = matrix[row][col] / matrix[rank][col];
for (int j = 0; j <= n; j++) {
matrix[row][j] -= factor * matrix[rank][j];
}
}
}
rank++;
}
return rank;
}
}
Python
class Solution:
def solveEquationsMatrix(self, equations: str) -> Optional[Dict[str, int]]:
lines = equations.strip().split('\n')
variables: Set[str] = set()
# Collect all variables
for line in lines:
self._collectVariables(line, variables)
varList = sorted(list(variables)) # For consistent ordering
varIndex = {var: i for i, var in enumerate(varList)}
n = len(varList)
m = len(lines)
# Create augmented matrix
matrix: List[List[float]] = [[0.0] * (n + 1) for _ in range(m)]
for i, line in enumerate(lines):
if not self._parseEquationToMatrix(line, matrix[i], varIndex):
return None
# Gaussian elimination
rank = self._gaussianElimination(matrix, n)
# Check for inconsistency
for i in range(rank, m):
if abs(matrix[i][n]) > 1e-9:
return None # Inconsistent
if rank < n:
return None # Underdetermined
# Back substitution
solution: List[float] = [0.0] * n
for i in range(n - 1, -1, -1):
solution[i] = matrix[i][n]
for j in range(i + 1, n):
solution[i] -= matrix[i][j] * solution[j]
solution[i] /= matrix[i][i]
# Convert to integer solution
result: Dict[str, int] = {}
for i, variable in enumerate(varList):
val = solution[i]
if abs(val - round(val)) > 1e-9:
return None # Non-integer solution
result[variable] = int(round(val))
return result
def _collectVariables(self, line: str, variables: Set[str]) -> None:
cleaned = line.replace(' ', '')
i = 0
while i < len(cleaned):
if cleaned[i].isalpha():
variable = ""
while i < len(cleaned) and cleaned[i].isalnum():
variable += cleaned[i]
i += 1
variables.add(variable)
else:
i += 1
def _parseEquationToMatrix(self, line: str, row: List[float],
varIndex: Dict[str, int]) -> bool:
cleaned = line.replace(' ', '')
if '=' not in cleaned:
return False
left, right = cleaned.split('=', 1)
# Parse left side
if self._isVariableMatrix(left):
row[varIndex[left]] = 1
else:
try:
row[len(row) - 1] = float(left)
except ValueError:
return False
# Parse right side and subtract
self._parseExpressionToMatrix(right, row, varIndex, -1)
return True
def _parseExpressionToMatrix(self, expr: str, row: List[float],
varIndex: Dict[str, int], multiplier: float) -> None:
sign = multiplier
pos = 0
while pos < len(expr):
if pos < len(expr) and expr[pos] == '+':
sign = multiplier
pos += 1
elif pos < len(expr) and expr[pos] == '-':
sign = -multiplier
pos += 1
nextOp = pos
while nextOp < len(expr) and expr[nextOp] not in '+-':
nextOp += 1
if nextOp > pos:
term = expr[pos:nextOp]
if self._isVariableMatrix(term):
row[varIndex[term]] += sign
else:
try:
row[len(row) - 1] += sign * float(term)
except ValueError:
pass # Skip invalid terms
pos = nextOp
def _isVariableMatrix(self, term: str) -> bool:
return len(term) > 0 and term[0].isalpha()
def _gaussianElimination(self, matrix: List[List[float]], n: int) -> int:
rank = 0
for col in range(n):
if rank >= len(matrix):
break
# Find pivot
pivot = -1
for row in range(rank, len(matrix)):
if abs(matrix[row][col]) > 1e-9:
pivot = row
break
if pivot == -1:
continue
# Swap rows
if pivot != rank:
matrix[rank], matrix[pivot] = matrix[pivot], matrix[rank]
# Eliminate
for row in range(len(matrix)):
if row != rank and abs(matrix[row][col]) > 1e-9:
factor = matrix[row][col] / matrix[rank][col]
for j in range(n + 1):
matrix[row][j] -= factor * matrix[rank][j]
rank += 1
return rank
Complexity
- ⏰ Time complexity:
O(n³ + n²m)where n is the number of variables and m is the number of equations. Gaussian elimination is O(n³), equation parsing is O(nm). - 🧺 Space complexity:
O(nm)for the augmented matrix storing n variables across m equations plus additional data structures for variable mapping.