Subtract Two Single-Variable Polynomials in Data Structure
Polynomial subtraction is an important mathematical operation in data structures where two polynomials containing the same variable are subtracted to produce a resultant polynomial.
In data structures, a polynomial can be represented using arrays or linked lists. Each polynomial term consists of a coefficient and an exponent. To subtract two polynomials, we compare the exponents of their terms and subtract the corresponding coefficients.
For example, consider two polynomials:
Their subtraction is:
After simplifying:
What is Polynomial Subtraction?
Polynomial subtraction is the process of subtracting one polynomial from another by subtracting the coefficients of terms having the same exponent.
A polynomial is an algebraic expression containing variables, coefficients, and non-negative integer exponents.
A general single-variable polynomial is represented as:
Where:
- a0,a1,…,an represent coefficients.
- x represents the variable.
- n represents the highest degree of the polynomial.
Important rules of polynomial subtraction:
- Arrange both polynomials in descending order of exponents.
- Identify terms having the same exponent.
- Subtract the coefficient of the second polynomial from the first.
- If a term is missing, consider its coefficient as zero.
- Remove terms whose resulting coefficients are zero.
- Write the final polynomial in descending order of exponents.
Representation of Polynomials in Data Structures
Before implementing polynomial subtraction, it is important to understand how polynomials are represented in a computer.
Two commonly used representations are:
A. Array Representation
In array representation, each array index represents an exponent, and the corresponding array element stores its coefficient.
For example:
Its array representation is:
| Array Index (Exponent) | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Coefficient | 7 | 2 | 4 | 5 |
Here:
P[0] = 7represents the constant term.P[1] = 2represents the coefficient of x.P[2] = 4represents the coefficient of x².P[3] = 5represents the coefficient of x³.
B. Linked List Representation
In linked list representation, each node stores three pieces of information:
- Coefficient
- Exponent
- Pointer to the next node
For example:
Its linked list representation is:
[5 | 3 | next] → [4 | 2 | next] → [2 | 1 | next] → [7 | 0 | NULL]
Each node stores a coefficient and its corresponding exponent.
Note: Array representation is suitable for polynomials with relatively small degree ranges, whereas linked lists are useful when polynomials contain many missing powers or sparse terms.
Algorithm for Polynomial Subtraction
- Start.
- Read the coefficients of polynomial P and polynomial Q.
- Find the maximum degree between the two polynomials.
- Initialize a result array with zeros.
- Repeat for each exponent from 0 to the maximum degree:
- Get the coefficient of P for the current exponent. If unavailable, use 0.
- Get the coefficient of Q for the current exponent. If unavailable, use 0.
- Subtract the coefficients and store the result.
- Remove leading zero coefficients from the result.
- Display the resultant polynomial in descending order of exponents.
- Stop.
C Program to Subtract Two Polynomials Using Arrays
The following C program subtracts two single-variable polynomials using arrays. It handles missing terms, negative coefficients, and zero coefficients.
#include <stdio.h>
#define MAX 100
void subtractPolynomials(int p[], int q[],
int degreeP, int degreeQ) {
int result[MAX] = {0};
int maxDegree = (degreeP > degreeQ)
? degreeP : degreeQ;
// Subtract corresponding coefficients
for (int i = 0; i <= maxDegree; i++) {
int a = (i <= degreeP) ? p[i] : 0;
int b = (i <= degreeQ) ? q[i] : 0;
result[i] = a - b;
}
// Find actual degree of the result
while (maxDegree > 0 &&
result[maxDegree] == 0) {
maxDegree--;
}
// Display resultant polynomial
printf("Resultant Polynomial = ");
int first = 1;
for (int i = maxDegree; i >= 0; i--) {
int c = result[i];
if (c == 0)
continue;
if (!first) {
printf(c > 0 ? " + " : " - ");
} else if (c < 0) {
printf("-");
}
int absC = (c < 0) ? -c : c;
if (i == 0) {
printf("%d", absC);
} else {
if (absC != 1)
printf("%d", absC);
printf("x");
if (i > 1)
printf("^%d", i);
}
first = 0;
}
if (first)
printf("0");
printf("\n");
}
int main() {
// P(x) = 2x^3 + 5x^2 + 4x + 3
int p[] = {3, 4, 5, 2};
// Q(x) = 3x^3 + 2x + 5
int q[] = {5, 2, 0, 3};
subtractPolynomials(p, q, 3, 3);
return 0;
}
Output
Resultant Polynomial = -x^3 + 5x^2 + 2x - 2
Time Complexity of Polynomial Subtraction
| Operation | Time Complexity |
|---|---|
polynomialSubtraction() | O(max(degree1, degree2)) |
main() (overall) | O(max(degree1, degree2)) |
Space Complexity of Polynomial Subtraction
| Operation | Space Complexity |
|---|---|
polynomialSubtraction() | O(max(degree1, degree2) + 1) |
main() (overall) | O(max(degree1, degree2) + 1) |