Plus Convolution NTT Problem

Plus Convolution NTT Problem — ExecCode Hard DSA Practice

Solve the Plus Convolution NTT problem on ExecCode. Free online hard DSA practice in Two Pointers. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Frequency arrays a and b: c[k] is the number of ways i+j = k with weight a[i]b[j]. That is ordinary polynomial multiplication, done with FFT or NTT in n log n instead of n^2. Return c of length len(a)+len(b)-1. Empty input returns an empty list. You are given: a — first polynomial b — second Return coefficient list of the product. c[0] = a[0]b[0].

Examples

Input {'a': [1, 2], 'b': [3, 4]}; Output [3, 10, 8]. Input {'a': [2], 'b': [5]}; Output [10]. Input {'a': [0, 1, 0], 'b': [1, 0]}; Output [0, 1, 0, 0]

Constraints

Indices start at 0 Values are integers

Practice Plus Convolution NTT free on ExecCode. Browse DSA problems, topic map, and placement guides.