HW3: FFT

  1.  We are given an array A with n elements, where each element of A is an integer in the range [0,n]. We are also given an integer t. The algorithm must answer the following yes-or-no question:
    Do there exist indices i, j, k, not necessarily distinct, such that A[i] + A[j] + A[k] = t?
    Design an O(n \log n) time algorithm for this problem.
  2. Modify your algorithm to count the total number of ordered triples (i,j,k) for which the sum of entries is at most t.
Advertisements