Home » Data Structure » Subtraction of Single variable Polynomial : Algorithm and Program

Subtraction of Single variable Polynomial : Algorithm and Program

Last updated:

Support this post with a reaction:

6,096 views

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:

P(x)=7x3+5x2+4x+9 P(x)=7x^3+5x^2+4x+9

Q(x)=3x3+2x+5 Q(x)=3x^3+2x+5

Their subtraction is:

R(x)=P(x)−Q(x) R(x)=P(x)-Q(x)

R(x)=(7x3+5x2+4x+9) R(x)=(7x^3+5x^2+4x+9)

−(3x3+2x+5) -(3x^3+2x+5)

After simplifying:

R(x)=4x3+5x2+2x+4 \boxed{R(x)=4x^3+5x^2+2x+4}

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:

P(x)=anxn+an−1xn−1+⋯+a1x+a0 P(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0

Where:

  • a0,a1,…,an represent coefficients.
  • x represents the variable.
  • n represents the highest degree of the polynomial.

Important rules of polynomial subtraction:

  1. Arrange both polynomials in descending order of exponents.
  2. Identify terms having the same exponent.
  3. Subtract the coefficient of the second polynomial from the first.
  4. If a term is missing, consider its coefficient as zero.
  5. Remove terms whose resulting coefficients are zero.
  6. 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:

P(x)=5x3+4x2+2x+7 P(x)=5x^3+4x^2+2x+7

Its array representation is:

Array Index (Exponent)0123
Coefficient7245

Here:

  • P[0] = 7 represents the constant term.
  • P[1] = 2 represents the coefficient of x.
  • P[2] = 4 represents the coefficient of x².
  • P[3] = 5 represents 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:

P(x)=5x3+4x2+2x+7 P(x)=5x^3+4x^2+2x+7

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

  1. Start.
  2. Read the coefficients of polynomial P and polynomial Q.
  3. Find the maximum degree between the two polynomials.
  4. Initialize a result array with zeros.
  5. 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.
  6. Remove leading zero coefficients from the result.
  7. Display the resultant polynomial in descending order of exponents.
  8. 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

OperationTime Complexity
polynomialSubtraction()O(max(degree1, degree2))
main() (overall)O(max(degree1, degree2))

Space Complexity of Polynomial Subtraction

OperationSpace Complexity
polynomialSubtraction()O(max(degree1, degree2) + 1)
main() (overall)O(max(degree1, degree2) + 1)