Solve the Equation (LeetCode)

-
Problem is here: https://leetcode.com/problems/solve-the-equation/#/description, or copied/pasted:

Solve a given equation and return the value of x in the form of string "x=#value". The equation contains only '+', '-' operation, the variable x and its coefficient.
If there is no solution for the equation, return "No solution".
If there are infinite solutions for the equation, return "Infinite solutions".
If there is exactly one solution for the equation, we ensure that the value of x is an integer.
Example 1:
Input: "x+5-3+x=6+x-2"
Output: "x=2"
Example 2:
Input: "x=x"
Output: "Infinite solutions"
Example 3:
Input: "2x=x"
Output: "x=0"
Example 4:
Input: "2x+3x-6x=x+2"
Output: "x=-1"
Example 5:
Input: "x=x+2"
Output: "No solution"

This is a problem of attention to details and modularization. The approach taken is to write two modules: the first one counts the "x"s given a leg of the equation. The second one counts the literals (numbers). Both are very similar, but with some diffs. They both perform tight string manipulation - it is important to be attentive to the boundaries, corner cases and the many different "states" of the string. Once you nail these two methods (and test them thoroughly in isolation), then the main method becomes rather straightforward. Code is below - cheers, Marcelo.


public class Solution
{
public string SolveEquation(string equation)
{
if (String.IsNullOrEmpty(equation)) return "No solution";

 string[] parts = equation.Split('=');

 int x = CountXs(parts[0]) - CountXs(parts[1]);
int literals = CountLiterals(parts[1]) - CountLiterals(parts[0]);

 if (x == 0 && literals == 0)
{
return "Infinite solutions";
}
else if (x == 0)
{
return "No solution";
}
else
{
return "x=" + (literals / x).ToString();
}
}

 private int CountLiterals(string equationPart)
{
if (String.IsNullOrEmpty(equationPart)) return 0;

 int retVal = 0;
int signal = 1;

 int partialVal = 0;
int index = 0;
while (index < equationPart.Length)
{
if (equationPart[index] == '-' || equationPart[index] == '+')
{
retVal = (signal * partialVal) + retVal;
partialVal = 0;
signal = (equationPart[index] == '-') ? -1 : 1;
}
else if (equationPart[index] >= '0' && equationPart[index] <= '9')
{
partialVal = 10 * partialVal + (int)(equationPart[index] - '0');
if (index + 1 >= equationPart.Length)
{
retVal = (signal * partialVal) + retVal;
partialVal = 0;
}
}
else if (equationPart[index] == 'x')
{
partialVal = 0;
}
index++;
}

 return retVal;
}

 private int CountXs(string equationPart)
{
if (String.IsNullOrEmpty(equationPart)) return 0;

 int retVal = 0;
for (int i = 0; i < equationPart.Length; i++)
{
if (equationPart[i] == 'x')
{
if (i == 0) retVal++;
else
{
if (equationPart[i - 1] == '+') retVal++;
else if (equationPart[i - 1] == '-') retVal--;
else
{
int val = 0;
int index = i - 1;
int mul = 1;
while (index >= 0 && equationPart[index] >= '0' && equationPart[index] <= '9')
{
val += mul * (int)(equationPart[index] - '0');
mul *= 10;
index--;
}
if (index < 0 || equationPart[index] == '+') retVal += val;
else if (equationPart[index] == '-') retVal -= val;
}
}
}
}

 return retVal;
}
}

Comments

  1. TarasDecember 3, 2017 at 11:05 PM

    If not for you, I'd be lazy to even try this problem, since it's fairly easy in terms of algorithmic complexity, but is a good coding exercise. My lazy attempt is below:

    class Solution {
    public:
    string solveEquation(const string& equation) {
    int sign = 1;
    int x_coeff = 0;
    int val = 0;
    int last_num = -1;
    int last_op_sign = 1;
    auto get_last_num = [&](int default_value) { return last_num == -1 ? default_value : last_num; };
    for (char ch : equation) {
    switch (ch) {
    case '=':
    val += last_op_sign * sign * last_num;
    last_num = -1;
    last_op_sign = 1;
    sign = -1;
    break;
    case '+':
    case '-':
    val += last_op_sign * sign * get_last_num(0);
    last_num = -1;
    last_op_sign = ch == '-' ? -1 : 1;
    break;
    case 'x':
    x_coeff += last_op_sign * sign * get_last_num(1);
    last_num = 0;
    break;
    default:
    last_num = get_last_num(0) * 10 + (ch - '0');
    break;
    }
    }
    val += last_op_sign * sign * last_num;
    if (x_coeff == 0) return val == 0 ? "Infinite solutions" : "No solution";
    if (x_coeff < 0) {
    x_coeff *= -1;
    val *= -1;
    }
    val *= -1;
    val /= x_coeff;
    return "x=" + to_string(val);
    }
    };

    Thanks for helping me fight my natural laziness :)
    Cheers,
    Taras

    ReplyDelete

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

Prompt Engineering and LeetCode

-
Image
With AI it becomes super interesting to try to "guide" it to solve a coding (LeetCode) problem. An example would be this one here:  The Knight’s Tour - LeetCode 2664. The Knight’s Tour Medium 11 0 Add to List Share Given two positive integers  m  and  n  which are the height and width of a  0-indexed  2D-array  board , a pair of positive integers  (r, c)  which is the starting position of the knight on the board. Your task is to find an order of movements for the knight, in a manner that every cell of the  board  gets visited  exactly  once (the starting cell is considered visited and you  shouldn't  visit it again). Return  the array   board   in which the cells' values show the order of visiting the cell starting from 0 (the initial place of the knight). Note that a  knight  can  move  from cell  (r1, c1)  to cell  (r2, c2)  if  0 <= r2 <= m - 1  and  0 <= c2 <= n - 1  and  min(abs(r1 - r2), abs(c1 - c2)) = 1  and  max(abs(r1 - r2), abs(c1 - c2)) = 2 .  
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more