In this guide, you will get 640. Solve the Equation LeetCode Solution with the best time and space complexity. The solution to Solve the Equation problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Solve a given equation and return the value of ‘x’ in the form of a string “x=#value”. The equation contains only ‘+’, ‘-‘ operation, the variable ‘x’ and its coefficient. You should return “No solution” if there is no solution for the equation, or “Infinite solutions” if there are infinite solutions for the equation.
If there is exactly one solution for the equation, we ensure that the value of ‘x’ is an integer.
3 <= equation.length <= 1000
equation has exactly one '='.
equation consists of integers with an absolute value in the range [0, 100] without any leading zeros, and the variable 'x'.
The input is generated that if there is a single solution, it will be an integer.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
640. Solve the Equation LeetCode Solution in C++
class Solution {
public:
string solveEquation(string equation) {
const string lhsEquation = equation.substr(0, equation.find('='));
const string rhsEquation = equation.substr(equation.find('=') + 1);
const auto& [lhsCoefficient, lhsConstant] = calculate(lhsEquation);
const auto& [rhsCoefficient, rhsConstant] = calculate(rhsEquation);
const int coefficient = lhsCoefficient - rhsCoefficient;
const int constant = rhsConstant - lhsConstant;
if (coefficient == 0 && constant == 0)
return "Infinite solutions";
if (coefficient == 0 && constant != 0)
return "No solution";
return "x=" + to_string(constant / coefficient);
}
private:
pair<int, int> calculate(const string& s) {
int coefficient = 0;
int constant = 0;
int num = 0;
int sign = 1;
for (int i = 0; i < s.length(); ++i) {
const char c = s[i];
if (isdigit(c))
num = num * 10 + (c - '0');
else if (c == '+' || c == '-') {
constant += sign * num;
sign = c == '+' ? 1 : -1;
num = 0;
} else {
if (i > 0 && num == 0 && s[i - 1] == '0')
continue;
coefficient += num == 0 ? sign : sign * num;
num = 0;
}
}
return {coefficient, constant + sign * num};
}
}; /* code provided by PROGIEZ */
640. Solve the Equation LeetCode Solution in Java
class Solution {
public String solveEquation(String equation) {
String[] equations = equation.split("=");
int[] lhs = calculate(equations[0]);
int[] rhs = calculate(equations[1]);
int coefficient = lhs[0] - rhs[0];
int constant = rhs[1] - lhs[1];
if (coefficient == 0 && constant == 0)
return "Infinite solutions";
if (coefficient == 0 && constant != 0)
return "No solution";
return "x=" + constant / coefficient;
}
private int[] calculate(final String s) {
int coefficient = 0;
int constant = 0;
int num = 0;
int sign = 1;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (Character.isDigit(c))
num = num * 10 + (c - '0');
else if (c == '+' || c == '-') {
constant += sign * num;
sign = c == '+' ? 1 : -1;
num = 0;
} else {
if (i > 0 && num == 0 && s.charAt(i - 1) == '0')
continue;
coefficient += num == 0 ? sign : sign * num;
num = 0;
}
}
return new int[] {coefficient, constant + sign * num};
}
} // code provided by PROGIEZ
640. Solve the Equation LeetCode Solution in Python
class Solution:
def solveEquation(self, equation: str) -> str:
def calculate(s: str) -> tuple:
coefficient = 0
constant = 0
num = 0
sign = 1
for i, c in enumerate(s):
if c.isdigit():
num = num * 10 + int(c)
elif c in '+-':
constant += sign * num
sign = 1 if c == '+' else -1
num = 0
else:
if i > 0 and num == 0 and s[i - 1] == '0':
continue
coefficient += sign if num == 0 else sign * num
num = 0
return coefficient, constant + sign * num
lhsEquation, rhsEquation = equation.split('=')
lhsCoefficient, lhsConstant = calculate(lhsEquation)
rhsCoefficient, rhsConstant = calculate(rhsEquation)
coefficient = lhsCoefficient - rhsCoefficient
constant = rhsConstant - lhsConstant
if coefficient == 0 and constant == 0:
return "Infinite solutions"
if coefficient == 0 and constant != 0:
return "No solution"
return "x=" + str(constant // coefficient) # code by PROGIEZ
