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);
  }
}