title: Determining if there exists numbers n1, n2 in a, b and n3 in c such that n1 + n2 = n3 [ftt, polynomial multiplication]
body: <p>Hello I am working on a problem that seems to be out of my league so any tips, pointers to reading materials etc. are really appreciated. That being said here is the problem:</p>
  <p>given 3 subsets of numbers a, b, c ⊆ {0, ..., n}. In nlog(n) check if there exists numbers n1, n2 in a, b and n3 in c where n1 + n2 = n3.</p>
  <p>I am given the hint to convert a and b to polynomial coefficients and to use polynomial multiplication using ftt to multiply the coefficients of a and b.</p>
  <p>Now where I am stuck is after getting the result of the polynomial multiplication, what do I do next?</p>
  <p>Thank you in advanced.</p>
  <pre><code>from numpy.fft import fft, ifft
  from numpy import real, imag
  
  def polynomial_multiply(a_coeff_list, b_coeff_list):
      # Return the coefficient list of the multiplication 
      # of the two polynomials 
      # Returned list must be a list of floating point numbers.
      # list from complex to reals by using the 
      # real function in numpy
      len_a = len(a_coeff_list)
      len_b = len(b_coeff_list)
      for i in range(len_a-1):
          b_coeff_list.append(0)
      for i in range(len_b-1):
          a_coeff_list.append(0)
      a_fft = fft(a_coeff_list)
      b_fft = fft(b_coeff_list)
      c = []
      for i in range(len(a_fft)):
          c.append(a_fft[i] * b_fft[i])
      inverse_c = ifft(c)
      return real(inverse_c)
  
  # inputs sets a, b, c
  # return True if there exist n1 in a, n2 in B such that n1+n2 in C
  # return False otherwise
  # number n which signifies the maximum number in a, b, c
  def check_sum_exists(a, b, c, n):
      a_coeffs = [0]*n
      b_coeffs = [0]*n 
      # convert sets a, b into polynomials as provided in the hint
      # a_coeffs and b_coeffs should contain the result
      i = 0
      for item in a:
          a_coeffs[i] = item
          i += 1
      i = 0
      for item in b:
          b_coeffs[i] = item
          i += 1
      # multiply them together
      c_coeffs = polynomial_multiply(a_coeffs, b_coeffs)
      # now this is where i am lost
      # how to determine with c_coeffs?
      return False
      # return True/False
  </code></pre>