Given two polynomials represented by two arrays, write a function that adds given two polynomials.
Example:
Input: A[] = {5, 0, 10, 6}
B[] = {1, 2, 4}
Output: sum[] = {6, 2, 14, 6}
The first input array represents "5 + 0x^1 + 10x^2 + 6x^3"
The second array represents "1 + 2x^1 + 4x^2"
And Output is "6 + 2x^1 + 14x^2 + 6x^3"
We strongly recommend minimizing your browser and try this yourself first.
Addition is simpler than multiplication of polynomials. We initialize the result as one of the two polynomials, then we traverse the other polynomial and add all terms to the result.
add(A[0..m-1], B[0..n01])
1) Create a sum array sum[] of size equal to maximum of 'm' and 'n'
2) Copy A[] to sum[].
3) Traverse array B[] and do following for every element B[i]
sum[i] = sum[i] + B[i]
4) Return sum[].
The following is the implementation of the above algorithm.
C++
// Simple C++ program to add two polynomials#include <iostream>using namespace std;// A utility function to return maximum of two integersint max(int m, int n) { return (m > n) ? m : n; }// A[] represents coefficients of first polynomial// B[] represents coefficients of second polynomial// m and n are sizes of A[] and B[] respectivelyint* add(int A[], int B[], int m, int n){ int size = max(m, n); int* sum = new int[size]; // Initialize the product polynomial for (int i = 0; i < m; i++) sum[i] = A[i]; // Take every term of first polynomial for (int i = 0; i < n; i++) sum[i] += B[i]; return sum;}// A utility function to print a polynomialvoid printPoly(int poly[], int n){ for (int i = 0; i < n; i++) { cout << poly[i]; if (i != 0) cout << "x^" << i; if (i != n - 1) cout << " + "; }}// Driver program to test above functionsint main(){ // The following array represents polynomial 5 + 10x^2 + // 6x^3 int A[] = { 5, 0, 10, 6 }; // The following array represents polynomial 1 + 2x + // 4x^2 int B[] = { 1, 2, 4 }; int m = sizeof(A) / sizeof(A[0]); int n = sizeof(B) / sizeof(B[0]); cout << "First polynomial is \n"; printPoly(A, m); cout << "\nSecond polynomial is \n"; printPoly(B, n); int* sum = add(A, B, m, n); int size = max(m, n); cout << "\nsum polynomial is \n"; printPoly(sum, size); return 0;} |
Java
// Java program to add two polynomialsclass GFG {// A utility function to return maximum of two integers static int max(int m, int n) { return (m > n) ? m : n; }// A[] represents coefficients of first polynomial // B[] represents coefficients of second polynomial // m and n are sizes of A[] and B[] respectively static int[] add(int A[], int B[], int m, int n) { int size = max(m, n); int sum[] = new int[size];// Initialize the product polynomial for (int i = 0; i < m; i++) { sum[i] = A[i]; }// Take ever term of first polynomial for (int i = 0; i < n; i++) { sum[i] += B[i]; } return sum; }// A utility function to print a polynomial static void printPoly(int poly[], int n) { for (int i = 0; i < n; i++) { System.out.print(poly[i]); if (i != 0) { System.out.print("x^" + i); } if (i != n - 1) { System.out.print(" + "); } } }// Driver program to test above functions public static void main(String[] args) { // The following array represents polynomial 5 + 10x^2 + 6x^3 int A[] = {5, 0, 10, 6}; // The following array represents polynomial 1 + 2x + 4x^2 int B[] = {1, 2, 4}; int m = A.length; int n = B.length; System.out.println("First polynomial is"); printPoly(A, m); System.out.println("\nSecond polynomial is"); printPoly(B, n); int sum[] = add(A, B, m, n); int size = max(m, n); System.out.println("\nsum polynomial is"); printPoly(sum, size); }} |
Python3
# Simple Python 3 program to add two# polynomials# A utility function to return maximum # of two integers# A[] represents coefficients of first polynomial# B[] represents coefficients of second polynomial# m and n are sizes of A[] and B[] respectivelydef add(A, B, m, n): size = max(m, n); sum = [0 for i in range(size)] # Initialize the product polynomial for i in range(0, m, 1): sum[i] = A[i] # Take ever term of first polynomial for i in range(n): sum[i] += B[i] return sum# A utility function to print a polynomialdef printPoly(poly, n): for i in range(n): print(poly[i], end = "") if (i != 0): print("x^", i, end = "") if (i != n - 1): print(" + ", end = "")# Driver Codeif __name__ == '__main__': # The following array represents # polynomial 5 + 10x^2 + 6x^3 A = [5, 0, 10, 6] # The following array represents # polynomial 1 + 2x + 4x^2 B = [1, 2, 4] m = len(A) n = len(B) print("First polynomial is") printPoly(A, m) print("\n", end = "") print("Second polynomial is") printPoly(B, n) print("\n", end = "") sum = add(A, B, m, n) size = max(m, n) print("sum polynomial is") printPoly(sum, size) # This code is contributed by# Sahil_Shelangia |
C#
// C# program to add two polynomialsusing System;class GFG { // A utility function to return maximum of two integers static int max(int m, int n) { return (m > n) ? m : n; } // A[] represents coefficients of first polynomial // B[] represents coefficients of second polynomial // m and n are sizes of A[] and B[] respectively static int[] add(int[] A, int[] B, int m, int n) { int size = max(m, n); int[] sum = new int[size]; // Initialize the product polynomial for (int i = 0; i < m; i++) { sum[i] = A[i]; } // Take ever term of first polynomial for (int i = 0; i < n; i++) { sum[i] += B[i]; } return sum; } // A utility function to print a polynomial static void printPoly(int[] poly, int n) { for (int i = 0; i < n; i++) { Console.Write(poly[i]); if (i != 0) { Console.Write("x^" + i); } if (i != n - 1) { Console.Write(" + "); } } } // Driver code public static void Main() { // The following array represents // polynomial 5 + 10x^2 + 6x^3 int[] A = {5, 0, 10, 6}; // The following array represents // polynomial 1 + 2x + 4x^2 int[] B = {1, 2, 4}; int m = A.Length; int n = B.Length; Console.WriteLine("First polynomial is"); printPoly(A, m); Console.WriteLine("\nSecond polynomial is"); printPoly(B, n); int[] sum = add(A, B, m, n); int size = max(m, n); Console.WriteLine("\nsum polynomial is"); printPoly(sum, size); }}//This Code is Contributed // by Mukul Singh |
PHP
<?php// Simple PHP program to add two polynomials// A[] represents coefficients of first polynomial// B[] represents coefficients of second polynomial// m and n are sizes of A[] and B[] respectivelyfunction add($A, $B, $m, $n){ $size = max($m, $n); $sum = array_fill(0, $size, 0); // Initialize the product polynomial for ($i = 0; $i < $m; $i++) $sum[$i] = $A[$i]; // Take ever term of first polynomial for ($i = 0; $i < $n; $i++) $sum[$i] += $B[$i]; return $sum;}// A utility function to print a polynomialfunction printPoly($poly, $n){ for ($i = 0; $i < $n; $i++) { echo $poly[$i]; if ($i != 0) echo "x^" . $i; if ($i != $n - 1) echo " + "; }}// Driver Code// The following array represents// polynomial 5 + 10x^2 + 6x^3$A = array(5, 0, 10, 6);// The following array represents // polynomial 1 + 2x + 4x^2$B = array(1, 2, 4);$m = count($A);$n = count($B);echo "First polynomial is \n";printPoly($A, $m);echo "\nSecond polynomial is \n";printPoly($B, $n);$sum = add($A, $B, $m, $n);$size = max($m, $n);echo "\nsum polynomial is \n";printPoly($sum, $size);// This code is contributed by chandan_jnu?> |
Javascript
<script>// Simple JavaScript program to add two// polynomials// A utility function to return maximum // of two integers// A[] represents coefficients of first polynomial// B[] represents coefficients of second polynomial// m and n are sizes of A[] and B[] respectively function add(A, B, m, n){ let size = Math.max(m, n); var sum = []; for (var i = 0; i < 10; i++) sum[i] = 0; // Initialize the product polynomial for(let i = 0;i<m;i++){ sum[i] = A[i]; } // Take ever term of first polynomial for (let i = 0;i<n;i++){ sum[i] += B[i]; } return sum; } // A utility function to print a polynomial function printPoly(poly, n){ let ans = ''; for(let i = 0;i<n;i++){ ans += poly[i]; if (i != 0){ ans +="x^ "; ans +=i; } if (i != n - 1){ ans += " + "; } } document.write(ans); } // Driver Code // The following array represents // polynomial 5 + 10x^2 + 6x^3 let A = [5, 0, 10, 6]; // The following array represents // polynomial 1 + 2x + 4x^2 let B = [1, 2, 4]; let m = A.length; let n = B.length; document.write("First polynomial is" + "</br>"); printPoly(A, m); document.write("</br>"); document.write("Second polynomial is" + "</br>"); printPoly(B, n); let sum = add(A, B, m, n); let size = Math.max(m, n); document.write("</br>"); document.write("sum polynomial is" + "</br>"); printPoly(sum, size); </script> |
Output:
First polynomial is 5 + 0x^1 + 10x^2 + 6x^3 Second polynomial is 1 + 2x^1 + 4x^2 Sum polynomial is 6 + 2x^1 + 14x^2 + 6x^3
Time complexity: O(m+n) where m and n are orders of two given polynomials.
Auxiliary Space: O(max(m, n))
Polynomial addition using Linked List
C++
// Program to add two polynomials represented// in linkedlist using recursion#include <iostream>using namespace std;// Node classclass Node {public: int coeff, power; Node* next; // Constructor of Node Node(int coeff, int power) { this->coeff = coeff; this->power = power; this->next = NULL; }};// Function to add polynomialsvoid addPolynomials(Node* head1, Node* head2){ // Checking if our list is empty if (head1 == NULL && head2 == NULL) return; // List contains elmements else if (head1->power == head2->power) { cout << " " << head1->coeff + head2->coeff << "x^" << head1->power << " "; addPolynomials(head1->next, head2->next); } else if (head1->power > head2->power) { cout << " " << head1->coeff << "x^" << head1->power << " "; addPolynomials(head1->next, head2); } else { cout << " " << head2->coeff << "x^" << head2->power << " "; addPolynomials(head1, head2->next); }}void insert(Node* head, int coeff, int power){ Node* new_node = new Node(coeff, power); while (head->next != NULL) { head = head->next; } head->next = new_node;}void printList(Node* head){ cout << "Linked List" << endl; while (head != NULL) { cout << " " << head->coeff << "x" << "^" << head->power; head = head->next; }}// Main functionint main(){ Node* head = new Node(5, 2); insert(head, 4, 1); Node* head2 = new Node(6, 2); insert(head2, 4, 1); printList(head); cout << endl; printList(head2); cout << endl << "Addition:" << endl; addPolynomials(head, head2); return 0;} |
Java
// java code for the above approach// Program to add two polynomials represented// in linkedlist using recursionimport java.util.*;// Node classclass Node { public int coeff, power; Node next; // Constructor of Node Node(int coeff, int power) { this.coeff = coeff; this.power = power; this.next = null; }}// Function to add polynomialspublic class Main { public static void addPolynomials(Node head1, Node head2) { // Checking if our list is empty if (head1 == null && head2 == null) return; // List contains elements else if (head1.power == head2.power) { System.out.print(" " + (head1.coeff + head2.coeff) + "x^" + head1.power + " "); addPolynomials(head1.next, head2.next); } else if (head1.power > head2.power) { System.out.print(" " + head1.coeff + "x^" + head1.power + " "); addPolynomials(head1.next, head2); } else { System.out.print(" " + head2.coeff + "x^" + head2.power + " "); addPolynomials(head1, head2.next); } } public static void insert(Node head, int coeff, int power) { Node new_node = new Node(coeff, power); while (head.next != null) { head = head.next; } head.next = new_node; } public static void printList(Node head) { System.out.println("Linked List"); while (head != null) { System.out.print(" " + head.coeff + "x" + "^" + head.power); head = head.next; } } // Main function public static void main(String[] args) { Node head = new Node(5, 2); insert(head, 4, 1); Node head2 = new Node(6, 2); insert(head2, 4, 1); printList(head); System.out.println(); printList(head2); System.out.println("\nAddition:"); addPolynomials(head, head2); }}// This code is contributed by Prince Kumar |
Python3
# Program to add two polynomials represented# in linkedlist using recursionclass Node: def __init__(self, coeff, power): self.coeff = coeff self.power = power self.next = None # Function to add polynomialsdef add_polynomials(head1, head2): if not head1 and not head2: return elif head1.power == head2.power: print(f' {head1.coeff + head2.coeff}x^{head1.power}', end='') add_polynomials(head1.next, head2.next) elif head1.power > head2.power: print(f' {head1.coeff}x^{head1.power}', end='') add_polynomials(head1.next, head2) else: print(f' {head2.coeff}x^{head2.power}', end='') add_polynomials(head1, head2.next)def insert(head, coeff, power): new_node = Node(coeff, power) while head.next: head = head.next head.next = new_nodedef print_list(head): print('Linked List') while head: print(f' {head.coeff}x^{head.power}', end='') head = head.nextif __name__ == '__main__': head = Node(5, 2) insert(head, 4, 1) head2 = Node(6, 2) insert(head2, 4, 1) print_list(head) print() print_list(head2) print('\nAddition:') add_polynomials(head, head2) |
C#
using System;class Node{ public int coeff, power; public Node next; // Constructor of Node public Node(int coeff, int power) { this.coeff = coeff; this.power = power; this.next = null; }}class Polynomial{ public static void AddPolynomials(Node head1, Node head2) { // Checking if our list is empty if (head1 == null && head2 == null) return; // List contains elements else if (head1.power == head2.power) { Console.Write(" " + (head1.coeff + head2.coeff) + "x^" + head1.power); AddPolynomials(head1.next, head2.next); } else if (head1.power > head2.power) { Console.Write(" " + head1.coeff + "x^" + head1.power); AddPolynomials(head1.next, head2); } else { Console.Write(" " + head2.coeff + "x^" + head2.power); AddPolynomials(head1, head2.next); } } public static void Insert(Node head, int coeff, int power) { Node new_node = new Node(coeff, power); while (head.next != null) { head = head.next; } head.next = new_node; } public static void PrintList(Node head) { Console.WriteLine("Linked List"); while (head != null) { Console.Write(" " + head.coeff + "x^" + head.power); head = head.next; } } public static void Main() { Node head = new Node(5, 2); Insert(head, 4, 1); Node head2 = new Node(6, 2); Insert(head2, 4, 1); PrintList(head); Console.WriteLine(); PrintList(head2); Console.WriteLine("\nAddition:"); AddPolynomials(head, head2); Console.ReadLine(); }} |
Javascript
// Program to add two polynomials represented// in linkedlist using recursion// Node classclass Node { constructor(coeff, power) { this.coeff = coeff; this.power = power; this.next = null; }}// Function to add polynomialsfunction addPolynomials(head1, head2) { // Checking if our list is empty if (head1 === null && head2 === null) { return; } // List contains elmements else if (head1.power === head2.power) { console.log(` ${head1.coeff + head2.coeff}x^${head1.power} `); addPolynomials(head1.next, head2.next); } else if (head1.power > head2.power) { console.log(` ${head1.coeff}x^${head1.power} `); addPolynomials(head1.next, head2); } else { console.log(` ${head2.coeff}x^${head2.power} `); addPolynomials(head1, head2.next); }}function insert(head, coeff, power) { const new_node = new Node(coeff, power); while (head.next !== null) { head = head.next; } head.next = new_node;}function printList(head) { console.log("Linked List"); while (head !== null) { console.log(` ${head.coeff}x^${head.power}`); head = head.next; }}// Main functionconst head = new Node(5, 2);insert(head, 4, 1);const head2 = new Node(6, 2);insert(head2, 4, 1);printList(head);console.log();printList(head2);console.log("\nAddition:\n");addPolynomials(head, head2); |
Output
Linked List 5x^2 4x^1 Linked List 6x^2 4x^1 Addition: 11x^2 8x^1
Time Complexity: O(m + n) where m and n are number of nodes in first and second lists respectively.
Auxiliary Space: O(m + n) where m and n are number of nodes in first and second lists respectively due to recursion.
This article is contributed by Harsh. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Implementation of a function that adds two polynomials represented as lists:
Approach
This implementation takes two arguments p1 and p2, which are lists representing the coefficients of two polynomials. The function returns a new list representing the sum of the two input polynomials.
The function first checks the lengths of the two input lists and pads the shorter list with zeros so that both lists have the same length. We then use the zip function to create pairs of corresponding coefficients from the two input lists, and the sum function to add the pairs together. The resulting sum is appended to a new list, which is returned at the end.
C++
#include <iostream>#include <vector>std::vector<int> add_polynomials(std::vector<int> p1, std::vector<int> p2) { int len1 = p1.size(); int len2 = p2.size(); if (len1 < len2) { p1.resize(len2, 0); } else { p2.resize(len1, 0); } std::vector<int> result(len1); for (int i = 0; i < len1; i++) { result[i] = p1[i] + p2[i]; } return result;}int main() { std::vector<int> p1 = {2, 0, 4, 6, 8}; std::vector<int> p2 = {0, 0, 1, 2}; std::vector<int> result = add_polynomials(p1, p2); for (int i = 0; i < result.size(); i++) { std::cout << result[i] << " "; } return 0;} |
Python3
def add_polynomials(p1, p2): len1, len2 = len(p1), len(p2) if len1 < len2: p1 += [0] * (len2 - len1) else: p2 += [0] * (len1 - len2) return [sum(x) for x in zip(p1, p2)]p1 = [2, 0, 4, 6, 8]p2 = [0, 0, 1, 2]print(add_polynomials(p1, p2)) |
Java
import java.util.*;public class PolynomialAddition { public static List<Integer> addPolynomials(List<Integer> p1, List<Integer> p2) { int len1 = p1.size(); int len2 = p2.size(); if (len1 < len2) { for (int i = 0; i < len2 - len1; i++) { p1.add(0); } } else { for (int i = 0; i < len1 - len2; i++) { p2.add(0); } } List<Integer> result = new ArrayList<Integer>(len1); for (int i = 0; i < len1; i++) { result.add(p1.get(i) + p2.get(i)); } return result; } public static void main(String[] args) { List<Integer> p1 = new ArrayList<Integer>(Arrays.asList(2, 0, 4, 6, 8)); List<Integer> p2 = new ArrayList<Integer>(Arrays.asList(0, 0, 1, 2)); List<Integer> result = addPolynomials(p1, p2); for (int i = 0; i < result.size(); i++) { System.out.print(result.get(i) + " "); } }} |
C#
using System;using System.Collections.Generic;using System.Linq;class Program { static List<int> AddPolynomials(List<int> p1, List<int> p2) { int len1 = p1.Count; int len2 = p2.Count; if (len1 < len2) { p1.AddRange(Enumerable.Repeat(0, len2 - len1)); } else { p2.AddRange(Enumerable.Repeat(0, len1 - len2)); } List<int> result = new List<int>(len1); for (int i = 0; i < len1; i++) { result.Add(p1[i] + p2[i]); } return result; } static void Main(string[] args) { List<int> p1 = new List<int> { 2, 0, 4, 6, 8 }; List<int> p2 = new List<int> { 0, 0, 1, 2 }; List<int> result = AddPolynomials(p1, p2); foreach (int coeff in result) { Console.Write(coeff + " "); } }} |
Javascript
function addPolynomials(p1, p2) { let len1 = p1.length; let len2 = p2.length; if (len1 < len2) { p1 = p1.concat(new Array(len2 - len1).fill(0)); } else { p2 = p2.concat(new Array(len1 - len2).fill(0)); } let result = new Array(len1); for (let i = 0; i < len1; i++) { result[i] = p1[i] + p2[i]; } return result;}let p1 = [2, 0, 4, 6, 8];let p2 = [0, 0, 1, 2];let result = addPolynomials(p1, p2);console.log(result.join(" ")); |
Output
[2, 0, 5, 8, 8]
time complexity: O(n), where n is the max of length of two polynomials
space complexity: O(n). where n is the max of length of two polynomials
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!
