Multiplication of two polynomials using Linked list in Java
Multiplication of two polynomials using Linked list in Java
When multiplying two polynomials expressed as linked lists, terms must be combined while adhering to the rules of polynomial multiplication. With a coefficient and an exponent, each node in the linked list represents a term in the polynomial. Each term in the first polynomial is multiplied by each term in the second polynomial, and like terms—terms with the same exponent—are then combined to multiply two polynomials.
![Multiplication of two polynomials using Linked list in Java](https://static.tutorialandexample.com/java/multiplication-of-two-polynomials-using-linked-list-in-java1.png)
Example 1
Input: First Polynomial: 3x^2 + 5x^1 + 6
Second Polynomial: 6x^1 + 8
Output: Resultant Polynomial: 18x^3 + 54x^2 + 76x^1 + 48
Example 2
Input: First Polynomial: 2x^3 + 4x^2
Second Polynomial: 3x^1 + 1x^0
Output: Resultant Polynomial: 6x^4 + 14x^3 + 4x^2
Example 3
Input: First Polynomial: 1x^1 + 1x^0
Second Polynomial: 1x^1 + 1x^0
Output: Resultant Polynomial: 1x^2 + 2x^1 + 1x^0
Example 4
Input: First Polynomial: 5x^4 + 3x^2
Second Polynomial: 6x^3 + 2x^1
Output: Resultant Polynomial: 30x^7 + 10x^5 + 18x^5 + 6x^3
Approach 1: Naive Approach
The naïve approach involves creating a new linked list to store the result. For each term in the first polynomial, multiply it by each term in the second polynomial and add the result to the new linked list. After all multiplications, combine the like terms.
Algorithm
Step 1: Create a Node class to represent each term in the polynomial with coefficient and exponent.
Step 2: Create a Polynomial class with methods to add a new term, multiply two polynomials, combine like terms, and display the polynomial.
Step 3: To multiply two polynomials:
Step 3.1: Iterate through each term of the first polynomial (poly1) and each term of the second polynomial (poly2).
Step 3.2: Multiply the coefficients and add the exponents to create a new term in the result polynomial (result).
Step 4: After all multiplications, combine like terms in the result polynomial to simplify the polynomial expression.
Step 5: Display the input polynomials and the resultant polynomial.
FileName: PolynomialMultiplication.java
class Node { int coeff; int exp; Node next; Node(int coeff, int exp) { this.coeff = coeff; // Coefficient of the term this.exp = exp; // Exponent of the term this.next = null; // Initialize next pointer to null } } class Polynomial { Node head; // Head of the linked list representing the polynomial // Method to add a new term to the polynomial void addTerm(int coeff, int exp) { Node newNode = new Node(coeff, exp); // Create a new node with the given coefficient and exponent if (head == null) { head = newNode; // If the list is empty, set the new node as the head } else { Node temp = head; while (temp.next != null) { temp = temp.next; // Traverse the list to find the last node } temp.next = newNode; // Append the new node to the end of the list } } // Method to multiply two polynomials Polynomial multiply(Polynomial poly) { Polynomial result = new Polynomial(); // Initialize the result polynomial Node p1 = this.head; // Start with the first term of the calling polynomial while (p1 != null) { Node p2 = poly.head; // Start with the first term of the parameter polynomial while (p2 != null) { result.addTerm(p1.coeff * p2.coeff, p1.exp + p2.exp); // Multiply coefficients and add exponents to add a new term to the result p2 = p2.next; // Move to the next term in the parameter polynomial } p1 = p1.next; // Move to the next term in the calling polynomial } // Combine like terms in the result result.combineLikeTerms(); return result; // Return the multiplied polynomial } // Method to combine like terms in the polynomial void combineLikeTerms() { Node ptr1, ptr2, prev; ptr1 = head; // Start with the head of the polynomial while (ptr1 != null && ptr1.next != null) { prev = ptr1; ptr2 = ptr1.next; // Start comparing with the next term while (ptr2 != null) { if (ptr1.exp == ptr2.exp) { ptr1.coeff += ptr2.coeff; // If exponents are equal, add coefficients prev.next = ptr2.next; // Remove the current node since it's combined with the previous one } else { prev = ptr2; } ptr2 = ptr2.next; // Move to the next term } ptr1 = ptr1.next; // Move to the next term for comparison } } // Method to display the polynomial void display() { Node temp = head; while (temp != null) { System.out.print(temp.coeff + "x^" + temp.exp); // Display coefficient and exponent if (temp.next != null) { System.out.print(" + "); // Add "+" between terms if not the last term } temp = temp.next; // Move to the next term } System.out.println(); // Print newline after displaying the polynomial } } public class PolynomialMultiplication { public static void main (String[] args) { // Create and initialize polynomials Polynomial poly1 = new Polynomial(); poly1.addTerm(3, 2); poly1.addTerm(5, 1); poly1.addTerm(6, 0); Polynomial poly2 = new Polynomial(); poly2.addTerm(6, 1); poly2.addTerm(8, 0); // Display input polynomials System.out.print("First Polynomial: "); poly1.display(); System.out.print("Second Polynomial: "); poly2.display(); // Multiply polynomials and display the result Polynomial result = poly1.multiply(poly2); System.out.print("Resultant Polynomial: "); result.display(); } }
Output
First Polynomial: 3x^2 + 5x^1 + 6x^0 Second Polynomial: 6x^1 + 8x^0 Resultant Polynomial: 18x^3 + 54x^2 + 76x^1 + 48x^0
Time Complexity: The time complexity of polynomial multiplication using linked lists is O(n*m), where n is the number of terms in the first polynomial and m is the number of terms in the second polynomial. This is because we perform n*m multiplications and possibly O(n+m) operations to combine like terms.
Space Complexity: The space complexity of an algorithm is O(n+m) since we create a new polynomial for the result and may need additional space for combining like terms.
Approach 2: Using HashMap
A HashMap is used to store the coefficients of the resulting polynomial. The key will be the exponent, and the value will be the sum of coefficients for that exponent. This approach simplifies combining like terms.
Algorithm
Step 1: Create a Node class to represent each term in the polynomial with coefficient and exponent.
Step 2: Create a Polynomial class with methods to add a new term and multiply two polynomials using a HashMap.
Step 3: To multiply two polynomials:
Step 3.1: Iterate through each term of the first polynomial (poly1) and each term of the second polynomial (poly2).
Step 3.2: Calculate the exponent and coefficient of the product term.
Step 3.3: Store the results in a HashMap with the exponent as the key and the coefficient as the value.
Step 4: Convert the HashMap back to a Polynomial linked list to represent the multiplied polynomial.
Step 5: Display the input polynomials and the resultant polynomial.
FileName: PolynomialMultiplicationHashMap.java
import java.util.HashMap; class Node { int coeff; int exp; Node next; Node(int coeff, int exp) { this.coeff = coeff; // Coefficient of the term this.exp = exp; // Exponent of the term this.next = null; // Initialize next pointer to null } } class Polynomial { Node head; // Head of the linked list representing the polynomial // Method to add a new term to the polynomial void addTerm(int coeff, int exp) { Node newNode = new Node(coeff, exp); // Create a new node with the given coefficient and exponent if (head == null) { head = newNode; // If the list is empty, set the new node as the head } else { Node temp = head; while (temp.next != null) { temp = temp.next; // Traverse the list to find the last node } temp.next = newNode; // Append the new node to the end of the list } } // Method to multiply two polynomials using HashMap Polynomial multiply(Polynomial poly) { HashMapresultMap = new HashMap<>(); // HashMap to store product terms Node p1 = this.head; // Start with the first term of the calling polynomial while (p1 != null) { Node p2 = poly.head; // Start with the first term of the parameter polynomial while (p2 != null) { int exp = p1.exp + p2.exp; // Calculate the exponent of the product term int coeff = p1.coeff * p2.coeff; // Calculate the coefficient of the product term resultMap.put(exp, resultMap.getOrDefault(exp, 0) + coeff); // Store the product term in the HashMap p2 = p2.next; // Move to the next term in the parameter polynomial } p1 = p1.next; // Move to the next term in the calling polynomial } // Convert the resultMap to a Polynomial linked list Polynomial result = new Polynomial(); for (int exp : resultMap.keySet()) { result.addTerm(resultMap.get(exp), exp); // Add terms from the HashMap to the result polynomial } return result; // Return the multiplied polynomial } // Method to display the polynomial void display() { Node temp = head; while (temp != null) { System.out.print(temp.coeff + "x^" + temp.exp); // Display coefficient and exponent if (temp.next != null) { System.out.print(" + "); // Add "+" between terms if not the last term } temp = temp.next; // Move to the next term } System.out.println(); // Print newline after displaying the polynomial } } public class PolynomialMultiplicationHashMap { public static void main(String[] args) { // Create and initialize polynomials Polynomial poly1 = new Polynomial(); poly1.addTerm(3, 2); poly1.addTerm(5, 1); poly1.addTerm(6, 0); Polynomial poly2 = new Polynomial(); poly2.addTerm(6, 1); poly2.addTerm(8, 0); // Display input polynomials System.out.print("First Polynomial: "); poly1.display(); System.out.print("Second Polynomial: "); poly2.display(); // Multiply polynomials and display the result Polynomial result = poly1.multiply(poly2); System.out.print("Resultant Polynomial: "); result.display(); } }
Output
First Polynomial: 3x^2 + 5x^1 + 6x^0 Second Polynomial: 6x^1 + 8x^0 Resultant Polynomial: 48x^0 + 76x^1 + 54x^2 + 18x^3
Time Complexity: The time complexity of an algorithm is O(n*m), where n is the number of terms in the first polynomial and m is the number of terms in the second polynomial. This is because we perform n*m multiplications and insertions into the HashMap.
Space Complexity: The space complexity of an algorithm is O(n+m) due to the HashMap storing the product terms, where n and m are the number of terms in the input polynomials.