# Check for common element in two arrays using FFT

My task ask me to check whether there is a common element in two arrays $$(x_1,x_2,…,x_n)$$, $$(y_1,y_2,…,y_n)$$ with $$x_i,y_i\in\mathbb{N}$$ using the Fast Fourier Transform(FFT). (I’m aware that there is a simple $$O(n\log(n))$$ algorithm to solve this problem using sorting and binary search.) The tasks hints that we should consider the following product to solve the problem: $$\prod_{i+j=n} (x_i-y_j)$$ The product is obviously zero if there is a common element, but I am still not sure how I could compute it faster via FFT.
… I know how to use FFT to multiply polynoms efficiently, but somehow I seem to overlook something.