Overview

We saw in class an N2 logN sorting-based solution to the 3-sum problem. Given a series of numbers a0, a1, ..., an1 the 3-sum problem consists in finding all triplets (ai, aj, ak) such that ai+aj+ak=0. For this task we consider a closely related version of this problem in which the goal consists in finding all the quadruples (ai, aj, ak, al) with ijkl that satisfy following condition: ai+aj=ak+al.

Tasks description

You will implement two solutions to this problem. Your first solution must use sorting to solve the problem and must achieve a complexity of O(n2logn). Your second solution must use hash tables to solve the problem and have a complexity of O(n2).

Implementation

Create two classes SumSort.java and SumHash.java that implement the two solutions mentioned above. Both programs should process their input using StdIn.java in the following format.

The first line contains a single integer n, the number of values to read. It is followed by a list of n integers a0, a1, ..., an1, one per line. Both programs must print out their results to the command line in the following format: the first value output is the number of quadruples found followed by all the quadruples in the form "i0 i1 i2 i3" printed on separate lines such that ai0+ai1=ai2+ai3, and i0