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.
[pastacode lang=”cpp” manual=”%2F%2F%20Simple%20C%2B%2B%20program%20to%20add%20two%20polynomials%0A%23include%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20utility%20function%20to%20return%20maximum%20of%20two%20integers%0Aint%20max(int%20m%2C%20int%20n)%20%7B%20%20return%20(m%20%3E%20n)%3F%20m%3A%20n%3B%20%7D%0A%20%0A%2F%2F%20A%5B%5D%20represents%20coefficients%20of%20first%20polynomial%0A%2F%2F%20B%5B%5D%20represents%20coefficients%20of%20second%20polynomial%0A%2F%2F%20m%20and%20n%20are%20sizes%20of%20A%5B%5D%20and%20B%5B%5D%20respectively%0Aint%20*add(int%20A%5B%5D%2C%20int%20B%5B%5D%2C%20int%20m%2C%20int%20n)%0A%7B%0A%20%20%20int%20size%20%3D%20max(m%2C%20n)%3B%0A%20%20%20int%20*sum%20%3D%20new%20int%5Bsize%5D%3B%0A%20%0A%20%20%20%2F%2F%20Initialize%20the%20porduct%20polynomial%0A%20%20%20for%20(int%20i%20%3D%200%3B%20i%3Cm%3B%20i%2B%2B)%0A%20%20%20%20%20sum%5Bi%5D%20%3D%20A%5Bi%5D%3B%0A%20%0A%20%20%20%2F%2F%20Take%20ever%20term%20of%20first%20polynomial%0A%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20sum%5Bi%5D%20%2B%3D%20B%5Bi%5D%3B%0A%20%0A%20%20%20return%20sum%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20print%20a%20polynomial%0Avoid%20printPoly(int%20poly%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20cout%20%3C%3C%20poly%5Bi%5D%3B%0A%20%20%20%20%20%20%20if%20(i%20!%3D%200)%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22x%5E%22%20%3C%3C%20i%20%3B%0A%20%20%20%20%20%20%20if%20(i%20!%3D%20n-1)%0A%20%20%20%20%20%20%20cout%20%3C%3C%20%22%20%2B%20%22%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20The%20following%20array%20represents%20polynomial%205%20%2B%2010x%5E2%20%2B%206x%5E3%0A%20%20%20%20int%20A%5B%5D%20%3D%20%7B5%2C%200%2C%2010%2C%206%7D%3B%0A%20%0A%20%20%20%20%2F%2F%20The%20following%20array%20represents%20polynomial%201%20%2B%202x%20%2B%204x%5E2%0A%20%20%20%20int%20B%5B%5D%20%3D%20%7B1%2C%202%2C%204%7D%3B%0A%20%20%20%20int%20m%20%3D%20sizeof(A)%2Fsizeof(A%5B0%5D)%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(B)%2Fsizeof(B%5B0%5D)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22First%20polynomial%20is%20%5Cn%22%3B%0A%20%20%20%20printPoly(A%2C%20m)%3B%0A%20%20%20%20cout%20%3C%3C%20%22%5CnSecond%20polynomial%20is%20%5Cn%22%3B%0A%20%20%20%20printPoly(B%2C%20n)%3B%0A%20%0A%20%20%20%20int%20*sum%20%3D%20add(A%2C%20B%2C%20m%2C%20n)%3B%0A%20%20%20%20int%20size%20%3D%20max(m%2C%20n)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22%5Cnsumuct%20polynomial%20is%20%5Cn%22%3B%0A%20%20%20%20printPoly(sum%2C%20size)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”C++ Program” highlight=”” provider=”manual”/]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”]