Given two polynomial numbers represented by a linked list. Write a function to perform their algebraic sum. Examples:
Input: 1st number = 5x^2 + 4x^1 + 2x^0 2nd number = 5x^1 + 5x^0 Output: 5x^2 + 9x^1 + 7x^0
Approach: The implementation uses map data structure so that all coefficients of same power value are added together and kept in key-value pairs inside a map. Below is the implementation of the above approach:
CPP
// C++ program for addition of two polynomials// represented as linked lists#include <bits/stdc++.h>using namespace std;// Structure of Node usedstruct Node { // Coefficient of the polynomial int coeff; // Power of the polynomial int pow; Node* next;};// Function to create new nodevoid create_node(int x, int y, struct Node** temp){ struct Node *r, *z; z = *temp; if (z == NULL) { r = (struct Node*)malloc(sizeof(struct Node)); r->coeff = x; r->pow = y; *temp = r; r->next = (struct Node*)malloc(sizeof(struct Node)); r = r->next; r->next = NULL; } else { r->coeff = x; r->pow = y; r->next = (struct Node*)malloc(sizeof(struct Node)); r = r->next; r->next = NULL; }}// Display Linked listvoid show(struct Node* node){ if (node == NULL) return; while (node->next != NULL) { printf("%dx^%d", node->coeff, node->pow); node = node->next; if (node->next != NULL) printf(" + "); }}/* Function to print the required sum of apolynomial p1 and p2 as specified in output */void addPolynomial(Node* p1, Node* p2){ map<int, int> mp; Node* temp1 = p1; Node* temp2 = p2; while (temp1 != NULL) { // Add coefficients of same power value // map contains (powervalue, coeff) pair mp[temp1->pow] += temp1->coeff; temp1 = temp1->next; } while (temp2 != NULL) { mp[temp2->pow] += temp2->coeff; temp2 = temp2->next; } // Started from the end because higher power should // come first and there should be "+" symbol in between // so iterate up to second element and print last out of // the loop. for (auto it = (mp.rbegin()); it != prev(mp.rend()); ++it) cout << it->second << "x^" << it->first << " + "; cout << mp.begin()->second << "x^" << mp.begin()->first;}// Driver functionint main(){ struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL; // Create first list of 5x^2 + 4x^1 + 2x^0 create_node(5, 2, &poly1); create_node(4, 1, &poly1); create_node(2, 0, &poly1); // Create second list of 5x^1 + 5x^0 create_node(5, 1, &poly2); create_node(5, 0, &poly2); printf("1st Number: "); show(poly1); printf("\n2nd Number: "); show(poly2); poly = (struct Node*)malloc(sizeof(struct Node)); printf("\nAdded polynomial: "); // Function add two polynomial numbers addPolynomial(poly1, poly2); return 0;} |
Java
// Java program for addition of two polynomials// represented as linked listsimport java.util.*;// Structure of Node usedclass Node { // Coefficient of the polynomial int coeff; // Power of the polynomial int pow; Node next; Node(int coeff, int pow) { this.coeff = coeff; this.pow = pow; this.next = null; }}// Display Linked listclass LinkedList { Node head; // Function to create new node void create_node(int x, int y) { Node node = new Node(x, y); if (head == null) { head = node; } else { Node temp = head; while (temp.next != null) { temp = temp.next; } temp.next = node; } } void show() { Node node = head; while (node != null) { System.out.print(node.coeff + "x^" + node.pow); node = node.next; if (node != null) { System.out.print(" + "); } } }}class Main { // Function to print the required sum of a // polynomial p1 and p2 as specified in output static void addPolynomial(Node p1, Node p2) { Map<Integer, Integer> mp = new TreeMap<>(Collections.reverseOrder()); Node temp1 = p1; Node temp2 = p2; while (temp1 != null) { // Add coefficients of same power value // map contains (powervalue, coeff) pair mp.put(temp1.pow, mp.getOrDefault(temp1.pow, 0) + temp1.coeff); temp1 = temp1.next; } while (temp2 != null) { mp.put(temp2.pow, mp.getOrDefault(temp2.pow, 0) + temp2.coeff); temp2 = temp2.next; } // Started from the end because higher power should // come first and there should be "+" symbol in between // so iterate up to second element and print last out of // the loop. boolean first = true; for (Map.Entry<Integer, Integer> entry : mp.entrySet()) { int pow = entry.getKey(); int coeff = entry.getValue(); if (first) { System.out.print(coeff + "x^" + pow); first = false; } else { System.out.print(" + " + coeff + "x^" + pow); } } } // Driver function public static void main(String[] args) { LinkedList poly1 = new LinkedList(); LinkedList poly2 = new LinkedList(); // Create first list of 5x^2 + 4x^1 + 2x^0 poly1.create_node(5, 2); poly1.create_node(4, 1); poly1.create_node(2, 0); // Create second list of 5x^1 + 5x^0 poly2.create_node(5, 1); poly2.create_node(5, 0); System.out.print("1st Number: "); poly1.show(); System.out.print("\n2nd Number: "); poly2.show(); System.out.print("\nAdded polynomial: "); // Function add two polynomial numbers addPolynomial(poly1.head, poly2.head); }}// This code is contributed by Prajwal Kandekar |
Python3
# Python program for addition of two polynomials# represented as linked lists# Structure of Node usedclass Node: # Coefficient of the polynomial def __init__(self, coeff, pow): self.coeff = coeff # Power of the polynomial self.pow = pow self.next = None# Function to create new nodedef create_node(x, y): r = Node(x, y) r.next = None return r# Display Linked listdef show(node): if node is None: return while node.next is not None: print(f"{node.coeff}x^{node.pow}", end="") print(" + ", end="") node = node.next if node.next is not None: print(" ", end="") print(f"{node.coeff}x^{node.pow}")# Function to print the required sum of a # polynomial p1 and p2 as specified in outputdef addPolynomial(p1, p2): mp = {} temp1 = p1 temp2 = p2 while temp1 is not None: # Add coefficients of same power value # map contains (powervalue, coeff) pair mp[temp1.pow] = mp.get(temp1.pow, 0) + temp1.coeff temp1 = temp1.next while temp2 is not None: mp[temp2.pow] = mp.get(temp2.pow, 0) + temp2.coeff temp2 = temp2.next # Started from the end because higher power should # come first and there should be "+" symbol in between # so iterate up to second element and print last out of # the loop. for power in sorted(mp.keys(), reverse=True): print(f"{mp[power]}x^{power}", end="") if power != sorted(mp.keys(), reverse=True)[-1]: print(" + ", end="")# Driver functionif __name__ == "__main__": poly1 = None poly2 = None poly = None # Create first list of 5x^2 + 4x^1 + 2x^0 poly1 = create_node(5, 2) poly1.next = create_node(4, 1) poly1.next.next = create_node(2, 0) # Create second list of 5x^1 + 5x^0 poly2 = create_node(5, 1) poly2.next = create_node(5, 0) print("1st Number: ", end="") show(poly1) print("2nd Number: ", end="") show(poly2) print("Added polynomial: ", end="") # Function to add two polynomial numbers addPolynomial(poly1, poly2) |
C#
using System;using System.Collections.Generic;using System.Linq;// Structure of Node usedpublic class Node{ // Coefficient of the polynomial public int coeff; // Power of the polynomial public int pow; public Node next;}public class PolynomialAddition{ // Function to create a new node public static Node CreateNode(int x, int y) { Node r = new Node(); r.coeff = x; r.pow = y; r.next = null; return r; } // Display Linked list public static void Show(Node node) { if (node == null) return; while (node.next != null) { Console.Write($"{node.coeff}x^{node.pow}"); node = node.next; if (node.next != null) Console.Write(" + "); } } /* Function to print the required sum of a polynomial p1 and p2 as specified in output */ public static void AddPolynomial(Node p1, Node p2) { Dictionary<int, int> mp = new Dictionary<int, int>(); Node temp1 = p1; Node temp2 = p2; while (temp1 != null) { // Add coefficients of the same power value if (!mp.ContainsKey(temp1.pow)) mp[temp1.pow] = temp1.coeff; else mp[temp1.pow] += temp1.coeff; temp1 = temp1.next; } while (temp2 != null) { if (!mp.ContainsKey(temp2.pow)) mp[temp2.pow] = temp2.coeff; else mp[temp2.pow] += temp2.coeff; temp2 = temp2.next; } // Started from the end because higher power should // come first and there should be "+" symbol in between // so iterate up to the second element and print the last out of the loop. foreach (var item in mp.OrderByDescending(x => x.Key)) Console.Write($"{item.Value}x^{item.Key} + "); } // Driver function public static void Main() { Node poly1 = null; Node poly2 = null; // Create the first list of 5x^2 + 4x^1 + 2x^0 poly1 = CreateNode(5, 2); poly1.next = CreateNode(4, 1); poly1.next.next = CreateNode(2, 0); // Create the second list of 5x^1 + 5x^0 poly2 = CreateNode(5, 1); poly2.next = CreateNode(5, 0); Console.Write("1st Number: "); Show(poly1); Console.Write("\n2nd Number: "); Show(poly2); Console.Write("\nAdded polynomial: "); // Function to add two polynomial numbers AddPolynomial(poly1, poly2); }} |
Javascript
class Node { constructor(coeff, pow) { this.coeff = coeff; this.pow = pow; this.next = null; }}// Function to create a new nodefunction createNode(x, y, temp) { let r = new Node(x, y); if (temp === null) { temp = r; } else { let current = temp; while (current.next !== null) { current = current.next; } current.next = r; } return temp;}// Display Linked listfunction show(node) { if (node === null) { return; } while (node.next !== null) { console.log(`${node.coeff}x^${node.pow}`); node = node.next; if (node.next !== null) { console.log(" + "); } }}// Function to print the required sum of a polynomial p1 and p2function addPolynomial(p1, p2) { let result = null; let currentResult = null; let current1 = p1; let current2 = p2; while (current1 !== null && current2 !== null) { if (current1.pow === current2.pow) { let sumCoeff = current1.coeff + current2.coeff; if (sumCoeff !== 0) { result = createNode(sumCoeff, current1.pow, result); current1 = current1.next; current2 = current2.next; } } else if (current1.pow > current2.pow) { result = createNode(current1.coeff, current1.pow, result); current1 = current1.next; } else { result = createNode(current2.coeff, current2.pow, result); current2 = current2.next; } } // Add any remaining terms from p1 and p2 while (current1 !== null) { result = createNode(current1.coeff, current1.pow, result); current1 = current1.next; } while (current2 !== null) { result = createNode(current2.coeff, current2.pow, result); current2 = current2.next; } // Reverse the result linked list for correct order let reversedResult = null; while (result !== null) { let next = result.next; result.next = reversedResult; reversedResult = result; result = next; } return reversedResult;}// Driver functionfunction main() { let poly1 = null; let poly2 = null; // Create the first list of 5x^2 + 4x^1 + 2x^0 poly1 = createNode(5, 2, poly1); poly1 = createNode(4, 1, poly1); poly1 = createNode(2, 0, poly1); // Create the second list of 5x^1 + 5x^0 poly2 = createNode(5, 1, poly2); poly2 = createNode(5, 0, poly2); console.log("1st Number: "); show(poly1); console.log("2nd Number: "); show(poly2); console.log("Added polynomial: "); let result = addPolynomial(poly1, poly2); show(result);}main(); |
Time Complexity: O((m + n)log(m+n)) where m and n are numbers of nodes in first and second lists respectively and we are using a map for adding the coefficients extra log(m+n) factor is added.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
