640. Solve the Equation
Problem Description
The problem asks us to solve a linear algebraic equation for the variable x
and to return the solution as a string in the format "x=#value". An algebraic equation is a mathematical statement that uses constants, variables (in this case, x
), and arithmetic operations (addition and subtraction) to set two expressions equal to each other. The given equation will only contain these operations and the variable x
with a possible coefficient (a number multiplying the variable).
The task involves three potential outcomes:
-
There is exactly one solution to the equation. The problem assures us that if this is the case, the value of 'x' will be an integer, and we should return it in the specified format.
-
There is no solution to the equation. If the terms involving the variable
x
cancel each other out, but the constant terms do not, this means the equation is contradictory (for example, "0x=3" has no solution), and we should return "No solution". -
There are infinite solutions to the equation. If both the variable terms and the constant terms cancel out, the equation is true for all values of
x
(for example, "0x=0"), and we should return "Infinite solutions".
Intuition
To solve the equation, we can first split it into two parts, the left-hand side (LHS) and the right-hand side (RHS), at the equals sign ('='). Each side will be evaluated independently to simplify the equation to determine the x
term's coefficient and the constant term.
The core intuition behind the solution involves these steps:
-
Separating each term: We iterate through each character of the equation string. Every time we encounter a '+' or '-', we know that a new term is starting. A term can be a coefficient of
x
(like "2x", "-3x", or "+x") or just a constant (like "5" or "-6"). -
Interpret each term: For each term, we need to decide if it contains
x
or not. If it does, we extract the coefficient; if it's just a number, we handle it as a constant term. The coefficient ofx
can be potentially positive or negative, which is indicated by the sign immediately preceding the term. We take this sign into account when adding to the total coefficient ofx
. -
Consolidating terms: After translating all terms on one side of the equation into their numeric values (with the appropriate signs), we sum up all the
x
coefficients to get the net coefficient ofx
for one side, and we sum up all the constants to get the net constant for that side. -
Equating and Simplifying: After we have the net
x
coefficient and constant for both the LHS and RHS, we can consolidate the equation such that allx
terms are on one side and all constant terms are on the other side. This is done by subtracting thex
coefficients and constant terms of one side from the other. -
Solving for
x
: If the netx
coefficient is not zero, we can solve forx
by dividing the net constants' difference by the netx
coefficients' difference. This will give us the value ofx
. -
Determining the Outcome: We check the net coefficients to see if there is one solution, no solution, or infinite solutions. If the net coefficient of
x
is zero and the constants are equal, there are infinite solutions. If the net coefficient ofx
is zero and the constants are not equal, there is no solution. Otherwise, we return the calculated value ofx
.
Learn more about Math patterns.
Solution Approach
The implementation of the solution follows a systematic approach to separately interpret the left-hand side and right-hand side of the equation, extract the coefficients of x
and the constant terms, subsequently process them, and finally evaluate the required solution (if it exists).
The solveEquation
function is the entry point of the solution. It receives the equation as an input string. It begins by defining an inner function f(s)
that takes one side of the equation (as a string s
) and performs the extraction and summation of x
coefficients and constants.
Inner Function f(s)
-
Initialization: Two variables
x
andy
are initialized to0
. Here,x
will hold the sum of the coefficients ofx
andy
will hold the sum of the constant terms. -
Handling Signage: If the string does not start with a minus sign ('-'), a plus sign ('+') is prepended to ensure consistency while parsing.
-
Parsing Terms: A while loop runs to parse each term in the string. If the sign is '+',
sign
is set to1
, otherwise to-1
. A nested while loop collects the characters that belong to the same term until it hits a '+' or '-' (or the end of the string). -
Process Each Term: Once a term is identified, the algorithm determines whether it contains an 'x'. Depending on this check, the term is processed as either a coefficient of
x
(adding or subtracting fromx
as controlled by thesign
) or a constant (adding or subtracting fromy
). Importantly, if onlyx
is present without a numeric coefficient, the coefficient is considered to be1
. -
Return Values: The function returns the net coefficients of
x
and the net constanty
for the given side of the equation.
Main Function Logic
-
Split Equation: The original equation string is split into two parts at the equals sign ('=') to get the left-hand side
a
and right-hand sideb
. -
Apply Inner Function: The function
f()
is called on both sides of the equation to obtain the respective sums ofx
coefficients and constants (x1
,y1
for LHS andx2
,y2
for RHS). -
Evaluate and Construct Solution:
- If both sides of the equation have the same net coefficient of
x
(x1 == x2
), it is either "Infinite solutions" (if the constants are the same) or "No solution" (if the constants differ). - If the net coefficients of
x
differ, we calculate the value ofx
by(y2 - y1) // (x1 - x2)
to find the solution and construct the result string in the format "x=#value".
By using simple arithmetic operations and control flow, the solution effectively reduces the algebraic equation to its simplest form to find the solution for the variable x
. This systematic approach allows the solution code to handle equations with varying coefficients and constant terms while determining the correct outcome among the three possible scenarios.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach: "3x+5=2x+10".
-
Initialization: We shall initialize
x
andy
to0
for both sides of the equation before processing. -
Handling Signage: Since the equation has "+" and "-" symbols clearly defining each term, we don't have to prepend any additional signs.
-
Split Equation: We split the equation at the '=' to get the left-hand side (LHS) "3x+5" and right-hand side (RHS) "2x+10".
-
Apply Inner Function
f(s)
to LHS:- Parse the LHS "3x+5"
- Identify and process terms "3x" and "+5"
- For "3x", set
x
to+3
(since the sign is +) - For "+5", set
y
to+5
- The LHS sums are
x1=3
andy1=5
-
Apply Inner Function
f(s)
to RHS:- Parse the RHS "2x+10"
- Identify and process terms "2x" and "+10"
- For "2x", set
x
to+2
- For "+10", set
y
to+10
- The RHS sums are
x2=2
andy2=10
-
Evaluate and Construct Solution:
- Since
x1=3
andx2=2
are not equal, we have one unique solution. - Calculate the value of
x
: (y2 - y1) / (x1 - x2) = (10 - 5) / (3 - 2) = 5 / 1 = 5 - Construct the result string in the format "x=#value" which is "x=5" for this example.
- Since
Using this approach, we have determined that the variable x
has the value of 5
in the equation "3x+5=2x+10". The consistent step-by-step method outlined in the solution approach allows us to parse the equation, identify and process terms, and evaluate the final solution with clarity.
Solution Implementation
1class Solution:
2 def solveEquation(self, equation: str) -> str:
3 # Helper function to process each side of the equation
4 def process_side(side):
5 coefficient_x = total_number = 0
6 if side[0] != '-':
7 side = '+' + side
8 idx, length = 0, len(side)
9 while idx < length:
10 sign = 1 if side[idx] == '+' else -1
11 idx += 1
12 j = idx
13 while j < length and side[j] not in '+-':
14 j += 1
15 term = side[idx:j]
16 # If the term ends with 'x', it contributes to coefficient of x
17 if term[-1] == 'x':
18 coefficient_x += sign * (int(term[:-1]) if len(term) > 1 else 1)
19 else:
20 # Otherwise, it contributes to the total number
21 total_number += sign * int(term)
22 idx = j
23 return coefficient_x, total_number
24
25 # Split the equation into left and right sides
26 left_side, right_side = equation.split('=')
27 # Process each side to get coefficients and numbers
28 coefficient_x_left, total_number_left = process_side(left_side)
29 coefficient_x_right, total_number_right = process_side(right_side)
30
31 # Handling cases of infinite solutions or no solution
32 if coefficient_x_left == coefficient_x_right:
33 if total_number_left == total_number_right:
34 return 'Infinite solutions'
35 else:
36 return 'No solution'
37 # Calculating value of x
38 return f'x={(total_number_right - total_number_left) // (coefficient_x_left - coefficient_x_right)}'
39
1class Solution {
2 public String solveEquation(String equation) {
3 // Split the equation into two parts, before and after the '=' sign.
4 String[] parts = equation.split("=");
5 // The left part of the equation is processed to get coefficients of x and the constant term.
6 int[] leftCoefficients = parsePart(parts[0]);
7 // The right part of the equation is processed to get coefficients of x and the constant term.
8 int[] rightCoefficients = parsePart(parts[1]);
9
10 // Assign the coefficients for easier readability.
11 int leftXCoefficient = leftCoefficients[0];
12 int leftConstant = leftCoefficients[1];
13 int rightXCoefficient = rightCoefficients[0];
14 int rightConstant = rightCoefficients[1];
15
16 // Check if the coefficients of x are the same on both sides.
17 if (leftXCoefficient == rightXCoefficient) {
18 // If constants are also the same, it means there are infinite solutions.
19 // Otherwise, it means there is no solution.
20 return leftConstant == rightConstant ? "Infinite solutions" : "No solution";
21 }
22 // If the coefficients of x are different, solve for x.
23 return "x=" + (rightConstant - leftConstant) / (leftXCoefficient - rightXCoefficient);
24 }
25
26 // Helper method to process each part of the equation.
27 private int[] parsePart(String part) {
28 // Initial values for coefficients of x and constant.
29 int xCoefficient = 0;
30 int constant = 0;
31
32 // Ensure we handle a leading '+' if it doesn't exist.
33 if (part.charAt(0) != '-') {
34 part = "+" + part;
35 }
36
37 // Initialize index to traverse the string.
38 int index = 0;
39 // Length of the current part of the equation.
40 int length = part.length();
41 // Traverse part of the equation to calculate coefficients.
42 while (index < length) {
43 // Determine the sign of the current part (+1 for positive, -1 for negative).
44 int sign = part.charAt(index) == '+' ? 1 : -1;
45 index++;
46 // Remember where the number starts.
47 int numberStartIndex = index;
48 // Locate the end of the number or 'x'.
49 while (index < length && part.charAt(index) != '+' && part.charAt(index) != '-') {
50 index++;
51 }
52 // Extract the current value (either a coefficient or constant).
53 String value = part.substring(numberStartIndex, index);
54 // Check if the value corresponds to x or a constant.
55 if (part.charAt(index - 1) == 'x') {
56 // Parse the coefficient of 'x' and apply the sign.
57 xCoefficient += sign * (value.length() > 1 ? Integer.parseInt(value.substring(0, value.length() - 1)) : 1);
58 } else {
59 // Parse the constant and apply the sign.
60 constant += sign * Integer.parseInt(value);
61 }
62 }
63 // Return the coefficients as an array.
64 return new int[] {xCoefficient, constant};
65 }
66}
67
1#include <string>
2#include <iostream>
3
4// Function to solve a linear equation of the form "ax+b=cx+d"
5std::string solveEquation(std::string equation) {
6 // Split the equation into its left and right parts at the '=' sign
7 size_t equalPos = equation.find('=');
8 std::string leftSide = equation.substr(0, equalPos);
9 std::string rightSide = equation.substr(equalPos + 1);
10
11 // Helper function to parse an expression (either left or right part of the equation)
12 auto parseExpression = [](const std::string &expr) -> std::pair<int, int> {
13 int coefficientX = 0; // Holds the coefficient of 'x'
14 int constantTerm = 0; // Holds the constant term
15 int currentNumber = 0; // Holds the current parsed number
16 int sign = 1; // Holds the current sign (1 for positive, -1 for negative)
17 bool isVariable = false; // Flag to check if we're parsing a variable 'x'
18
19 // Iterate over each character in the expression
20 for (char ch : expr) {
21 if (ch == '+' || ch == '-') {
22 // On encountering a '+' or '-', update the coefficients and constants
23 if (isVariable) {
24 coefficientX += currentNumber * sign;
25 } else {
26 constantTerm += currentNumber * sign;
27 }
28 // Reset for the next term
29 isVariable = false;
30 currentNumber = 0;
31 sign = ch == '+' ? 1 : -1;
32 } else if (ch == 'x') {
33 isVariable = true;
34 } else if (isdigit(ch)) {
35 // Accumulate the number from the digits
36 currentNumber = currentNumber * 10 + (ch - '0');
37 }
38 }
39
40 // After the loop, need to update the coefficients and constants one last time
41 if (isVariable) {
42 coefficientX += (currentNumber == 0 ? 1 : currentNumber) * sign;
43 } else {
44 constantTerm += currentNumber * sign;
45 }
46
47 return {coefficientX, constantTerm};
48 };
49
50 // Parse both sides of the equation to get coefficients and constant terms
51 std::pair<int, int> leftExpr = parseExpression(leftSide);
52 std::pair<int, int> rightExpr = parseExpression(rightSide);
53
54 // If the coefficient of 'x' is the same on both sides, check for no solution or infinite solutions
55 if (leftExpr.first == rightExpr.first) {
56 if (leftExpr.second == rightExpr.second) {
57 return "Infinite solutions";
58 } else {
59 return "No solution";
60 }
61 }
62
63 // If there is a valid solution for 'x', calculate and return the value
64 int xValue = (rightExpr.second - leftExpr.second) / (leftExpr.first - rightExpr.first);
65 return "x=" + std::to_string(xValue);
66}
67
1function solveEquation(equation: string): string {
2 // Split the equation into its left and right parts
3 const [leftSide, rightSide] = equation.split('=');
4
5 // Helper function to parse an expression (either left or right part of the equation)
6 const parseExpression = (expr: string): [number, number] => {
7 let coefficientX = 0; // holds the coefficient of x
8 let constantTerm = 0; // holds the constant term
9 let currentNumber = 0; // holds the current parsed number
10 let sign = 1; // holds the current sign (1 for positive, -1 for negative)
11 let isVariable = false; // flag to check if we're parsing a variable 'x'
12
13 // Iterate over each character in the expression
14 for (const char of expr) {
15 if (char === '+' || char === '-') {
16 // On encountering a '+' or '-', update the coeffs and constants
17 if (isVariable) {
18 coefficientX += currentNumber * sign;
19 } else {
20 constantTerm += currentNumber * sign;
21 }
22 // Reset for the next term
23 isVariable = false;
24 currentNumber = 0;
25 sign = char === '+' ? 1 : -1;
26 } else if (char === 'x') {
27 isVariable = true;
28 } else {
29 // Accumulate the number from the digits
30 currentNumber = currentNumber * 10 + Number(char);
31 }
32 }
33
34 // After the loop, need to update the coeffs and constants one last time
35 if (isVariable) {
36 coefficientX += (currentNumber || 1) * sign; // Assign 1 if no number before x
37 } else {
38 constantTerm += currentNumber * sign;
39 }
40
41 return [coefficientX, constantTerm];
42 };
43
44 // Parse both sides of the equation
45 const leftExpr = parseExpression(leftSide);
46 const rightExpr = parseExpression(rightSide);
47
48 // If the coefficient of x is the same on both sides, check for no or infinite solutions
49 if (leftExpr[0] === rightExpr[0]) {
50 if (leftExpr[1] === rightExpr[1]) {
51 return 'Infinite solutions';
52 } else {
53 return 'No solution';
54 }
55 }
56
57 // If there is a valid solution for x, calculate and return the value
58 return `x=${(rightExpr[1] - leftExpr[1]) / (leftExpr[0] - rightExpr[0])}`;
59}
60
Time and Space Complexity
The given Python code defines a function solveEquation
which solves a linear equation in the form of a string and returns the result. The computational complexity analysis is as follows:
Time Complexity:
The function f(s)
within the solveEquation
function is responsible for evaluating each side of the equation. Let's call the length of the input equation n
.
-
The function iterates over each character of the input equation string at most once, which results in
O(n)
time complexity for the parsing steps. -
The operation split('='), which separates the equation into the left and right sides, executes in
O(n)
time. -
The function
f(s)
is called twice, once for each side of the equation. Each call iterates the string with length proportional to the length of that side – this remains within overallO(n)
time. -
The operations to calculate the values of
x
andy
are constant-time arithmetic operations, thus do not increase the complexity class. -
The final arithmetic operations to calculate the value of
x
are also constant-time operations.
Combining all these steps, the overall time complexity of the solveEquation
function is O(n)
, where n
is the length of the equation string.
Space Complexity:
-
The space complexity is
O(1)
for the variablesx
,y
,sign
,v
,x1
,y1
,x2
,y2
,a
, andb
as their space requirement does not scale with the size of the input. -
Temporary variables
i
,j
, ands
, when assigned the slices of the input string, also do not increase the space complexity as these are reference assignments to parts of the original string and don't require additional space proportional to the size of the input string. -
There is no additional data structure that grows with the input size. The space required is only for a fixed number of variables and their fixed-size contents.
-
The auxiliary space used also does not depend on the input size, as it only involves a small number of fixed-size integer variables.
Considering all of the above points, the overall space complexity of the solveEquation
function is O(1)
– constant space complexity, as the space required does not scale with the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.