Build the Equation

Problem

Table: Terms

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


+-------------+------+
| Column Name | Type |
+-------------+------+
| power       | int  |
| factor      | int  |
+-------------+------+
power is the column with unique values for this table.
Each row of this table contains information about one term of the equation.
power is an integer in the range [0, 100].
factor is an integer in the range [-100, 100] and cannot be zero.

You have a very powerful program that can solve any equation of one variable in the world. The equation passed to the program must be formatted as follows:

The left-hand side (LHS) should contain all the terms.
The right-hand side (RHS) should be zero.
Each term of the LHS should follow the format "<sign><fact>X^<pow>" where:
- <sign> is either "+" or "-".
- <fact> is the absolute value of the factor.
- <pow> is the value of the power.
If the power is 1, do not add "^<pow>".
- For example, if power = 1 and factor = 3, the term will be "+3X".
If the power is 0, add neither "X" nor "^<pow>".
- For example, if power = 0 and factor = -3, the term will be "-3".
The powers in the LHS should be sorted in descending order.

Write a solution to build the equation.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


Input: 
Terms table:
+-------+--------+
| power | factor |
+-------+--------+
| 2     | 1      |
| 1     | -4     |
| 0     | 2      |
+-------+--------+
Output: 
+--------------+
| equation     |
+--------------+
| +1X^2-4X+2=0 |
+--------------+

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


Input: 
Terms table:
+-------+--------+
| power | factor |
+-------+--------+
| 4     | -4     |
| 2     | 1      |
| 1     | -1     |
+-------+--------+
Output: 
+-----------------+
| equation        |
+-----------------+
| -4X^4+1X^2-1X=0 |
+-----------------+

Follow up: What will be changed in your solution if the power is not a primary key but each power should be unique in the answer?

Solution

Method 1 – String Construction with Sorting

Intuition

We need to construct the equation string by sorting the terms by power in descending order and formatting each term according to the rules. This is a direct string manipulation problem with careful attention to formatting.

Approach

Select all terms from the Terms table.
Sort the terms by power in descending order.
For each term:
- If power is 0, append the factor as a signed integer.
- If power is 1, append the factor followed by ‘X’ (no power).
- Otherwise, append the factor followed by ‘X^’ and the power.
Concatenate all terms into a single string.
Append ‘=0’ at the end.
Return the result as the equation column.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


SELECT
  GROUP_CONCAT(
    CASE
      WHEN power = 0 THEN CONCAT(
        IF(factor > 0, '+', ''), factor
      )
      WHEN power = 1 THEN CONCAT(
        IF(factor > 0, '+', ''), factor, 'X'
      )
      ELSE CONCAT(
        IF(factor > 0, '+', ''), factor, 'X^', power
      )
    END
    ORDER BY power DESC
    SEPARATOR ''
  ) AS equation
FROM Terms;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


# Assume terms is a list of (power, factor) tuples
class Solution:
    def buildEquation(self, terms: list[tuple[int, int]]) -> str:
        terms.sort(reverse=True)
        ans = ''
        for p, f in terms:
            if p == 0:
                ans += ('+' if f > 0 else '') + str(f)
            elif p == 1:
                ans += ('+' if f > 0 else '') + str(f) + 'X'
            else:
                ans += ('+' if f > 0 else '') + str(f) + 'X^' + str(p)
        return ans + '=0'

Complexity

⏰ Time complexity: O(n log Nn for sorting n items
🧺 Space complexity: O(n) for the result string

Problem#

Examples#

Solution#

Method 1 – String Construction with Sorting#

Intuition#

Approach#

Code#

Complexity#