Given two polynomials represented by two arrays that contains the coefficients of poynomials, returns the polynomial in form of array formed after multiplication of given polynomials.
Example 1:
Input:
M = 4, N = 3
Arr1 = {1 , 0, 3, 2}
Arr2 = {2, 0, 4}
Output: {2, 0, 10, 4, 12, 8}
Explaination: 
First polynomial: 
1 + 0x^{1} + 3x^{2} + 2x^{3}
Second polynomial: 
2 + 0x^{1} + 4x^{2}
Product polynomial:
2 + 0x^{1} + 10x^{2} + 4x^{3} + 12x^{4} + 8x^{5}
Example 2:
Input:
M = 5, N = 4
Arr1 = {1, 9, 3, 4, 7}
Arr1 = {4, 0, 2, 5}
Output: {4, 36, 14, 39, 79, 23, 34, 35}
Explaination: 
First polynomial: 
1 + 9x^{1} + 3x^{2} + 4x^{3 }+ 7x^{4}
Second polynomial: 
4 + 0x^{1} + 2x^{2 }+ 5x^{3}
Product polynomial:
4 + 36x^{1} + 14x^{2} + 39x^{3} + 79x^{4} + 23x^{5 }+ 34x^{6} + 35x^{7}
Your Task:
You don't need to read input or print anything. Your task is to complete the function polyMultiply() which takes the array Arr1[] and Arr2[]and their size M and N as input parameters and returns the polynomial in form of array formed after multiplication of given polynomials..
Expected Time Complexity: O(M*N)
Expected Auxiliary Space: O(M+N)
Constraints:
1 ≤ M, N ≤ 100
1 ≤  Arr1[i] , Arr2[i]  ≤ 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3
class Solution:
	def polyMultiply(self, Arr1, Arr2, M, N):
		# code here


Solutions:
class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		res = [0] * (M + N - 1)
		for i in range(M):
			for j in range(N):
				res[i + j] += Arr1[i] * Arr2[j]
		return res


import numpy

class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		return numpy.polymul(Arr1, Arr2)


import numpy as np

class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		a = np.array(Arr1)
		b = np.array(Arr2)
		return np.polymul(a, b)


def add(poly1, poly2):
	result = [0] * max(len(poly1), len(poly2))
	for i in range(len(result)):
		if i < len(poly1):
			result[i] += poly1[i]
		if i < len(poly2):
			result[i] += poly2[i]
	return result

def split(poly1, poly2):
	mid = max(len(poly1), len(poly2)) // 2
	return ((poly1[:mid], poly1[mid:]), (poly2[:mid], poly2[mid:]))

def increase_exponent(poly, n):
	return [0] * n + poly

def multiply_optimized(poly1, poly2):
	if len(poly1) == 0 or len(poly2) == 0:
		return []
	if len(poly1) == 1:
		return [poly1[0] * i for i in poly2]
	elif len(poly2) == 1:
		return [poly2[0] * i for i in poly1]
	((poly1_0, poly1_1), (poly2_0, poly2_1)) = split(list(poly1), list(poly2))
	polyX = multiply_optimized(poly1_0, poly2_0)
	polyY = add(multiply_optimized(poly1_0, poly2_1), multiply_optimized(poly1_1, poly2_0))
	polyZ = multiply_optimized(poly1_1, poly2_1)
	mid = max(len(poly1), len(poly2)) // 2
	return add(add(polyX, increase_exponent(polyY, mid)), increase_exponent(polyZ, 2 * mid))

class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		return multiply_optimized(Arr1, Arr2)


class Solution:

	def polyMultiply(self, arr1, arr2, m, n):
		l = [0] * (m + n - 1)
		cnt = 0
		for i in range(len(arr1)):
			cnt = i
			for j in range(len(arr2)):
				k = arr1[i] * arr2[j]
				l[cnt] = k + l[cnt]
				cnt += 1
		return l


class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		arr = [0] * (M + N - 1)
		start = 0
		for i in range(M):
			k = start
			for j in range(N):
				arr[k + j] += Arr1[i] * Arr2[j]
			start += 1
		return arr


class Solution:

	def polyMultiply(self, arr1, arr2, m, n):
		sub = [0] * 10000
		c = 0
		(arr1, arr2) = (arr1[::-1], arr2[::-1])
		for i in range(m):
			for j in range(n):
				k = arr1[i] * arr2[j]
				sub[c + j] += k
			ap = c + j + 1
			c += 1
		sub = sub[:ap]
		return sub[::-1]


class Solution:

	def polyMultiply(self, a, b, M, N):
		c = [0 for i in range(len(a) + len(b) - 1)]
		for i in range(len(a)):
			for j in range(len(b)):
				c[i + j] += a[i] * b[j]
		return c


from numpy import polymul as pm

class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		return pm(Arr1, Arr2)


class Solution:

	def polyMultiply(self, arr1, arr2, M, N):
		arr = [0] * (M + N - 1)
		for i in range(M):
			for j in range(N):
				arr[i + j] += arr1[i] * arr2[j]
		return arr


class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		result = []
		ans = []
		ans = [0] * (M + (N - 1))
		for _ in range(N):
			result.append([0] * (M + (N - 1)))
		for i in range(N):
			for j in range(M):
				result[i][j + i] = Arr2[i] * Arr1[j]
		for i in range(len(result[0])):
			for j in range(len(result)):
				ans[i] += result[j][i]
		return ans


import numpy as np

class Solution:

	def polyMultiply(self, a, b, n, m):
		c = np.array(a)
		d = np.array(b)
		return np.polymul(a, b)


class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		n = M + N - 1
		res = []
		for i in range(n):
			res.append(0)
		for i in range(M):
			for j in range(N):
				try:
					if i + j < len(res):
						t = res[i + j]
						res[i + j] = t + Arr1[i] * Arr2[j]
				except:
					print(i, j, res)
					pass
		return res


class Solution:

	def polyMultiply(self, a11, a22, m, n):
		a1 = []
		a2 = []
		for (i, j) in enumerate(a11):
			a1.append((i + 1, j))
		for (i, j) in enumerate(a22):
			a2.append((i + 1, j))
		d = {}
		for i in range(m):
			for j in range(n):
				(i1, b1) = a1[i]
				(i2, b2) = a2[j]
				i3 = i1 + i2
				b3 = b1 * b2
				d[i3] = b3 + d.get(i3, 0)
		abc = sorted(list(d.keys()))
		res = []
		for i in abc:
			res.append(d[i])
		return res


import numpy as np

class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		a1 = np.array(Arr1)
		a2 = np.array(Arr2)
		rx = [int(i) for i in np.polynomial.polynomial.polymul(a1, a2)]
		return rx
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(M, N) = input().split()
		M = int(M)
		N = int(N)
		Arr1 = input().split()
		for itr in range(M):
			Arr1[itr] = int(Arr1[itr])
		Arr2 = input().split()
		for itr in range(N):
			Arr2[itr] = int(Arr2[itr])
		ob = Solution()
		ans = ob.polyMultiply(Arr1, Arr2, M, N)
		for i in range(len(ans)):
			print(ans[i], end=' ')
		print()


class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		new_arr = [0] * (M + N - 1)
		for i in range(M):
			for j in range(N):
				prod = Arr1[i] * Arr2[j]
				new_arr[i + j] += prod
		return new_arr
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(M, N) = input().split()
		M = int(M)
		N = int(N)
		Arr1 = input().split()
		for itr in range(M):
			Arr1[itr] = int(Arr1[itr])
		Arr2 = input().split()
		for itr in range(N):
			Arr2[itr] = int(Arr2[itr])
		ob = Solution()
		ans = ob.polyMultiply(Arr1, Arr2, M, N)
		for i in range(len(ans)):
			print(ans[i], end=' ')
		print()


class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		Arr3 = []
		for i in range(M + N - 1):
			Arr3.append(0)
		for i in range(M):
			for j in range(N):
				for k in range(M + N - 1):
					if k == i + j:
						Arr3[k] = Arr3[k] + Arr1[i] * Arr2[j]
		return Arr3


class Solution:

	def append_zero(r, arr):
		for i in range(r):
			arr.append(0)

	def polyMultiply(self, Arr1, Arr2, M, N):
		result = [0] * (M + N - 1)
		for i in range(M):
			for j in range(N):
				result[i + j] += Arr1[i] * Arr2[j]
		return result


from collections import defaultdict

class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		d1 = defaultdict(lambda : 0)
		d2 = defaultdict(lambda : 0)
		for i in range(M):
			d1[i] = Arr1[i]
		for j in range(N):
			d2[j] = Arr2[j]
		d3 = defaultdict(lambda : 0)
		for i in range(M):
			for j in range(N):
				t = d1[i] * d2[j]
				c = i + j
				d3[c] += t
		out = []
		for x in d3:
			out.append(d3[x])
		return out


import numpy as np

class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		a1 = np.array(Arr1)
		a2 = np.array(Arr2)
		rx = np.polymul(a1, a2)
		return rx


class Solution:

	def polyMultiply(self, a, b, m, n):
		finalArr = [0] * (m + n - 1)
		for i in range(0, m, 1):
			for j in range(0, n, 1):
				finalArr[i + j] += a[i] * b[j]
		return finalArr


from collections import Counter

class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		k = {}
		s = {}
		f = {}
		l = []
		for i in range(M):
			k[i] = Arr1[i]
		for i in range(N):
			s[i] = Arr2[i]
		for (key, value) in k.items():
			k1 = key
			v1 = value
			for (key1, value1) in s.items():
				vv = v1 * value1
				kk = key1 + k1
				if kk not in f:
					f[kk] = vv
				else:
					f[kk] = f[kk] + vv
		for (k, v) in f.items():
			l.append(v)
		return l


class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		ans = []
		a = {}
		b = {}
		res = {}
		for i in range(M):
			a[i] = Arr1[i]
		for i in range(N):
			b[i] = Arr2[i]
		for (key, value) in a.items():
			value1 = value
			keys = key
			for (key, value) in b.items():
				bvalues = value1 * value
				bkeys = keys + key
				if bkeys not in res:
					res[bkeys] = bvalues
				else:
					res[bkeys] += bvalues
		i = 0
		for (key, value) in res.items():
			ans.append(value)
		return ans


import numpy as np

class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		a1 = np.array(Arr1)
		a2 = np.array(Arr2)
		rx = [int(i) for i in np.polynomial.polynomial.polymul(a1, a2)]
		return rx


class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		arr = [0] * (M + N - 1)
		for m in range(M):
			for n in range(N):
				arr[m + n] += Arr1[m] * Arr2[n]
		return arr


class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		prod = []
		for i in range(0, M + N):
			coef = 0
			for j in range(0, i + 1):
				if j < M and i - j < N:
					coef += Arr1[j] * Arr2[i - j]
			prod.append(coef)
		del prod[-1]
		return prod


import numpy

class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		rx = numpy.polynomial.polynomial.polymul(Arr1, Arr2)
		s = []
		for i in rx:
			s.append(int(i))
		return s


class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):

		def add(lis1, lis2, ind):
			i = j = 0
			lis_temp = []
			while j < ind:
				lis_temp.append(lis1[j])
				j += 1
			while ind < len(lis1):
				lis_temp.append(lis1[ind] + lis2[i])
				i += 1
				ind += 1
			lis_temp.append(lis2[len(lis2) - 1])
			return lis_temp
		result = []
		for i in range(N):
			temp = []
			for j in range(M):
				temp.append(Arr2[i] * Arr1[j])
			result.append(temp)
		resul = result[0]
		for i in range(1, len(result)):
			resul = add(resul, result[i], i)
		return resul


class Solution:

	def polyMultiply(self, A, B, m, n):
		prod = [0] * (m + n - 1)
		for i in range(m):
			for j in range(n):
				prod[i + j] += A[i] * B[j]
		return prod


class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		out = [0]
		out *= M + N - 1
		for (enum, i) in enumerate(Arr1):
			cursor = enum
			for j in Arr2:
				out[cursor] += i * j
				cursor += 1
		return out


class Solution:

	def multiply(self, a, b, lo, hi):
		if lo > hi:
			return []
		if lo == hi:
			val = 0
			for i in range(hi + 1):
				if i < len(a) and hi - i < len(b):
					val += a[i] * b[hi - i]
				elif i == len(a) - 1:
					val += a[i]
				elif hi - i == len(b) - 1:
					val += b[hi - i]
			return [val]
		mid = lo + hi >> 1
		(left, right) = (self.multiply(a, b, lo, mid), self.multiply(a, b, mid + 1, hi))
		for num in right:
			left.append(num)
		return left

	def polyMultiply(self, Arr1, Arr2, M, N):
		return self.multiply(Arr1, Arr2, 0, M + N - 2)


class Solution:

	def polyMultiply(self, arr1, arr2, m, n):
		arr = [0] * (m + n - 1)
		for i in range(m):
			count = i
			for j in range(n):
				arr[count] += arr1[i] * arr2[j]
				count += 1
		return arr


from collections import defaultdict

class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		d = defaultdict(lambda : 0)
		for ind1 in range(len(Arr1)):
			for ind2 in range(len(Arr2)):
				d[ind1 + ind2] += Arr1[ind1] * Arr2[ind2]
		l = list(d.items())
		l.sort(key=lambda x: x[0])
		res = []
		for i in l:
			res.append(i[1])
		return res


class Solution:

	def polyMultiply(self, Arr1, Arr2, M, N):
		c = []
		for x in range(N):
			for y in range(M):
				if x + y >= len(c):
					c.append(Arr2[x] * Arr1[y])
				else:
					c[x + y] += Arr2[x] * Arr1[y]
		return c