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[] = {5, 10, 30, 26, 52, 24}

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"

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[].
[ad type=”banner”]

The following is C++ implementation of above algorithm.

C++ Program
// 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 \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 << "\nsumuct polynomial is \n";
printPoly(sum, size);

return 0;
}

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.

[ad type=”banner”]