## 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 a_{1}x^{n}y^{m} + a_{2}x^{n-1}y^{m-1}+ . . . + a_{k}x^{n-k}y + . . . + a_{n}x + a_{n+1}.

The above polynomial is said to be a polynomial in two variables (x and y).

a_{1}x^{n} + a_{2}x^{n-1} + a_{3}x^{n-2} + . . . + a_{n-1}x + a_{n}

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:

**a _{1}x^{n} + a_{2}x^{n-1} + a_{3}x^{n-2} + . . . + a_{n-1}x + a_{n}**

**b**

_{1}x^{m}+ b_{2}x^{m-1}+ b_{3}x^{m-2}+ . . . + b_{m-1}x + b_{m}a is called the co-efficient of the term x^{n} and b is called the co-efficient of the term x^{m}

If n is equal to m then the resultant sum will have a term (a+b)x^{n} 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 .

1 2 3 4 |
public class PolynomialNode { float coefficient; int power; } |

## 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public void printPolynomial(List<PolynomialNode> p1) { float coefficient = 0.0f; int count = 0; for (PolynomialNode p : p1) { coefficient = p.coefficient; if (count > 0) System.out.print(coefficient >= 0 ? " + " : " - "); if (coefficient < 0) coefficient *= -1; System.out.print(coefficient + (p.power > 0 ? "x^" + p.power : "")); count++; } System.out.println(); } |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
private List<PolynomialNode> addOrSubtract(List<PolynomialNode> p1, List<PolynomialNode> p2, boolean add) { List<PolynomialNode> resultantPolymial = null; if (p1 == null || p2 == null) return null; else { resultantPolymial = new ArrayList<PolynomialNode>(); int i = 0, j = 0; PolynomialNode n = null; PolynomialNode pNode1 = null; PolynomialNode pNode2 = null; while (i < p1.size() && j < p2.size()) { pNode1 = p1.get(i); pNode2 = p2.get(j); if (p1.get(i).power == p2.get(j).power) { n = result(pNode1, pNode2, add); i++; j++; } else if (p1.get(i).power > p2.get(j).power) { n = result(pNode1, null, add); i++; } else { n = result(null, pNode2, add); j++; } resultantPolymial.add(n); } return resultantPolymial; } } |

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
private PolynomialNode result(PolynomialNode pNode1, PolynomialNode pNode2, boolean add) { PolynomialNode resultNode = null; if (pNode1 != null && pNode2 != null) { if (add) resultNode = new PolynomialNode(pNode1.coefficient + pNode2.coefficient, pNode1.power); else resultNode = new PolynomialNode(pNode1.coefficient - pNode2.coefficient, pNode1.power); else if (pNode1 == null) if (add) resultNode = new PolynomialNode(pNode2.coefficient, pNode2.power); else resultNode = new PolynomialNode(-1 * pNode2.coefficient, pNode2.power); else resultNode = new PolynomialNode(pNode1.coefficient, pNode1.power); return resultNode; } |

##### Multiply Method

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
private List<PolynomialNode> multiply(List<PolynomialNode> p1, List<PolynomialNode> p2) { if (p1 == null || p2 == null) return null; LinkedHashMap<Integer, PolynomialNode> map = new LinkedHashMap<Integer, PolynomialNode>(); PolynomialNode n1 = null; PolynomialNode n2 = null; PolynomialNode n = null; int sumPower = 0; for (int i = 0; i < p1.size(); i++) { n1 = p1.get(i); for (int j = 0; j < p2.size(); j++) { n2 = p2.get(j); if (n1.coefficient != 0 && n2.coefficient != 0) { sumPower = n1.power + n2.power; n = map.get(sumPower); if (n == null) n = new PolynomialNode(0, sumPower); n.coefficient += n1.coefficient * n2.coefficient; map.put(sumPower, n); } } } List<PolynomialNode> resultantPolynomial = new ArrayList<PolynomialNode>(); for (Entry<Integer, PolynomialNode> entry : map.entrySet()) resultantPolynomial.add(entry.getValue()); return resultantPolynomial; } |

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.