pythonalgorithmfftpolynomial-math# Determining if there exists numbers n1, n2 in a, b and n3 in c such that n1 + n2 = n3 [ftt, polynomial multiplication]

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:

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.

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.

Now where I am stuck is after getting the result of the polynomial multiplication, what do I do next?

Thank you in advanced.

```
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
```

Solution

Thanks to all who helped. I figured it out and hopefully this can help anyone who runs into a similar problem. The issue I had was I incorrectly assigned the coefficients for `a_coeffs`

and `b_coeffs`

.

Here is the solution which passed the tests for those interested.

```
from numpy.fft import fft, ifft
from numpy import real, imag
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
for coeff in a:
a_coeffs[coeff] = 1
for coeff in b:
b_coeffs[coeff] = 1
# multiply them together
c_coeffs = polynomial_multiply(a_coeffs, b_coeffs)
# use the result to solve the problem at hand
for coeff in c:
if c_coeffs[coeff] >= .5:
return True
return False
# return True/False
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.
# Please convert list from complex to reals by using the
# real function in numpy.
for i in range(len(a_coeff_list) - 1):
b_coeff_list.append(0)
for i in range(len(b_coeff_list) - 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])
return real(ifft(c))
```

- Python Jinja2 LaTeX Table
- Getting attributes of a class
- How can I print many significant figures in Python?
- How to allow list append() method to return the new list
- Calculate Last Friday of Month in Pandas
- Python type hint for Iterable[str] that isn't str
- How to iterate over a list in chunks
- How to exit the entire application from a Python thread?
- Running shell command and capturing the output
- How do I pass a variable by reference?
- Convert range(r) to list of strings of length 2 in python
- How can I get the start and end dates for each week?
- how to use send_message() in python-telegram-bot
- Python conditional replacement based on element type
- How can I count the number of items in an arbitrary iterable (such as a generator)?
- Find longest consecutive range of numbers in list
- Insert text in braces with asyncpg
- How does one put a link / url to the web-site's home page in Django?
- How to determine if a path is a subdirectory of another?
- Custom Keybindings for Ipython terminal
- FastAPI asynchronous background tasks blocks other requests?
- How to make sure that information from one file is duplicated into several text documents, without specific lines
- Installing a Python environment with Anaconda
- sklearn pipeline model predicting same results for all input
- Brew command not found after installing Anaconda Python
- How to get an XPath from selenium webelement or from lxml?
- Pipe PuTTY console to Python script
- How to align the axes of a figure in matplotlib?
- Persist ParentDocumentRetriever of langchain
- How to reset index in a pandas dataframe?