Program to add two polynomials

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 to minimize your browser and try this yourself first.
Addition is simpler than multiplication of polynomials. We initialize 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) Travers array B[] and do following for every element B[i]
          sum[i] = sum[i] + B[i]
4) Return sum[].

The following is implementation of above algorithm.

C++

// Simple C++ program to add two polynomials 
#include <iostream> 
using namespace std; 
  
// A utility function to return maximum of two integers 
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 
int *add(int A[], int B[], int m, int n) 
{ 
   int size = max(m, n); 
   int *sum = new int[size]; 
  
   // Initialize the porduct 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 
void 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 functions 
int 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
"; 
    printPoly(A, m); 
    cout << "
Second polynomial is
"; 
    printPoly(B, n); 
  
    int *sum = add(A, B, m, n); 
    int size = max(m, n); 
  
    cout << "
sum polynomial is
"; 
    printPoly(sum, size); 
  
    return 0; 
} 

Java

// Java program to add two polynomials 
  
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 porduct 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("
Second polynomial is"); 
        printPoly(B, n); 
        int sum[] = add(A, B, m, n); 
        int size = max(m, n); 
        System.out.println("
sum polynomial is"); 
        printPoly(sum, size); 
  
    } 
} 

/div>

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[] respectively 
def add(A, B, m, n): 
  
    size = max(m, n); 
    sum = [0 for i in range(size)] 
  
    # Initialize the porduct 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 polynomial 
def 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 Code 
if __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("
", end = "") 
    print("Second polynomial is") 
    printPoly(B, n) 
    print("
", 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 polynomials 
using 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 porduct 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("
Second polynomial is"); 
        printPoly(B, n); 
        int[] sum = add(A, B, m, n); 
        int size = max(m, n); 
        Console.WriteLine("
sum 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[] respectively 
function add($A, $B, $m, $n) 
{ 
    $size = max($m, $n); 
    $sum = array_fill(0, $size, 0); 
      
    // Initialize the porduct 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 polynomial 
function 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
"; 
printPoly($A, $m); 
echo "
Second polynomial is
"; 
printPoly($B, $n); 
  
$sum = add($A, $B, $m, $n); 
$size = max($m, $n); 
  
echo "
sum polynomial is
"; 
printPoly($sum, $size); 
  
// This code is contributed by chandan_jnu 
?> 

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 of the above algorithm and program is O(m+n) where m and n are orders of two given polynomials.

C++

Java

Python3

C#

PHP

tags:

You Might Also Like

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books