Polynomial Operations

Introduction

This is a famous interview question where it is asked to write program for simple arithmetic polynomial operations. The operation may include adding, subtracting and multiplication of two polynomials (mostly in one variable).

For those who want to refresh their knowledge of polynomials, I would include a section below:

Understanding Polynomials

Polynomials are mathematical expressions of the form a1xnym + a2xn-1ym-1+ . . . + akxn-ky + . . . + anx + an+1.
The above polynomial is said to be a polynomial in two variables (x and y).

a1xn + a2xn-1 + a3xn-2 + . . . + an-1x + an
This is a polynomial in one variable.

Technique for Polynomial Operations

Here is a detailed description on what does it mean to operate on polynomials. I will try to do it using a program.

For simplicity we will consider polynomials in one variable only. That means either we can get rid of the x terms or the y terms from the above polynomial.

So the scope of our problem reduces to writing a class which provides methods to perform the following:

  • Adding the first polynomial to the second and returning the result
  • Subtracting the second polynomial from the first one and returning the result
  • Multiplying the first polynomial to the second one and returning the result

Division is a special case of multiplication and similarly subtraction is a special case of addition. I am sure after showing you how to do these three operation, you will come up with the division in a second.

Idea behind Polynomial addition & subtraction

Given the following polynomials:
a1xn + a2xn-1 + a3xn-2 + . . . + an-1x + an
b1xm + b2xm-1 + b3xm-2 + . . . + bm-1x + bm

a is called the co-efficient of the term xn and b is called the co-efficient of the term xm
If n is equal to m then the resultant sum will have a term (a+b)xn and so on. This means that we always add the coefficients when the power of the variable is same.

Same is true for the subtraction as well.

Storing the polynomial

We can always define a PolynomialNode class to store one term of the single variable polynomial. Then we can have an ordered list which stores the nodes in decreasing order of the powers of .

Source Code

You can download the complete source code from the github repository for techieme. Still I will add some code here and explain if required.

Printing a Polynomial

Special care is taken to not print the sign if it is the first term in the polynomial. Also, printing the “+” and “-” sign is done using the second if check for coefficient.

Generic Add and Subtract Method

The above method is generically written for adding or subtracting two polynomial nodes based on a flag. It also uses a helper method result which is mentioned below:

Multiply Method

Notice the use of LinkedHashMap to store the multiplied nodes. This ensures the highest power nodes in the beginning of the map and low power nodes at the end. So at the end when we create a list from the map, we will always get the high power nodes first.

Conclusion

Polynomial Operations are really cool stuff and can be easily done, if we choose the right data structures. Division is similar to multiplication, we just need to take care of divide by zero etc.

Don’t forget to subscribe to TechieMe to get updates on latest posts.