package algs14;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac ThreeSum.java
 *  Execution:    java ThreeSum input.txt
 *  Data files:   http://algs4.cs.princeton.edu/14analysis/1Kints.txt
 *                http://algs4.cs.princeton.edu/14analysis/2Kints.txt
 *                http://algs4.cs.princeton.edu/14analysis/4Kints.txt
 *                http://algs4.cs.princeton.edu/14analysis/8Kints.txt
 *                http://algs4.cs.princeton.edu/14analysis/16Kints.txt
 *                http://algs4.cs.princeton.edu/14analysis/32Kints.txt
 *                http://algs4.cs.princeton.edu/14analysis/1Mints.txt
 *
 *  A program with cubic running time. Read in N integers
 *  and counts the number of triples that sum to exactly 0
 *  (ignoring integer overflow).
 *
 *  % java ThreeSum 1Kints.txt
 *  70
 *
 *  % java ThreeSum 2Kints.txt
 *  528
 *
 *  % java ThreeSum 4Kints.txt
 *  4039
 *
 *************************************************************************/

public class ThreeSum {
	public static int ops;

	// print distinct triples (i, j, k) such that a[i] + a[j] + a[k] = 0
	public static void printAll(int[] a) {
		int N = a.length;
		for (int i = 0; i < N; i++) {
			for (int j = i+1; j < N; j++) {
				for (int k = j+1; k < N; k++) {
					if (a[i] + a[j] + a[k] == 0) {
						StdOut.println(a[i] + " " + a[j] + " " + a[k]);
					}
				}
			}
		}
	}

	// return number of distinct triples (i, j, k) such that a[i] + a[j] + a[k] = 0
	public static int count(int[] a) {
		int N = a.length;
		int cnt = 0;
		ops = 0;
		for (int i = 0; i < N; i++) {
			for (int j = i+1; j < N; j++) {
				for (int k = j+1; k < N; k++) {
					ops += 3;
					if (a[i] + a[j] + a[k] == 0) {
						cnt++;
					}
				}
			}
		}
		return cnt;
	}

	public static void main(String[] args)  {
		args = new String[] { "data/100ints.txt" };
		//        args = new String[] { "data/200ints.txt" };
		//        args = new String[] { "data/500ints.txt" };
		//        args = new String[] { "data/1Kints.txt" };
		//        args = new String[] { "data/2Kints.txt" };
		//        args = new String[] { "data/4Kints.txt" };
		//        args = new String[] { "data/8Kints.txt" };
		int[] a = new In(args[0]).readAllInts();

		//printAll (a);

		Stopwatch timer = new Stopwatch();
		int cnt = count(a);
		StdOut.println("elapsed time = " + timer.elapsedTime());
		StdOut.println(cnt);
	}
}