001package algs14;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac ThreeSum.java
005 *  Execution:    java ThreeSum input.txt
006 *  Data files:   http://algs4.cs.princeton.edu/14analysis/1Kints.txt
007 *                http://algs4.cs.princeton.edu/14analysis/2Kints.txt
008 *                http://algs4.cs.princeton.edu/14analysis/4Kints.txt
009 *                http://algs4.cs.princeton.edu/14analysis/8Kints.txt
010 *                http://algs4.cs.princeton.edu/14analysis/16Kints.txt
011 *                http://algs4.cs.princeton.edu/14analysis/32Kints.txt
012 *                http://algs4.cs.princeton.edu/14analysis/1Mints.txt
013 *
014 *  A program with cubic running time. Read in N integers
015 *  and counts the number of triples that sum to exactly 0
016 *  (ignoring integer overflow).
017 *
018 *  % java ThreeSum 1Kints.txt
019 *  70
020 *
021 *  % java ThreeSum 2Kints.txt
022 *  528
023 *
024 *  % java ThreeSum 4Kints.txt
025 *  4039
026 *
027 *************************************************************************/
028
029public class ThreeSum {
030        public static int ops;
031
032        // print distinct triples (i, j, k) such that a[i] + a[j] + a[k] = 0
033        public static void printAll(int[] a) {
034                int N = a.length;
035                for (int i = 0; i < N; i++) {
036                        for (int j = i+1; j < N; j++) {
037                                for (int k = j+1; k < N; k++) {
038                                        if (a[i] + a[j] + a[k] == 0) {
039                                                StdOut.println(a[i] + " " + a[j] + " " + a[k]);
040                                        }
041                                }
042                        }
043                }
044        }
045
046        // return number of distinct triples (i, j, k) such that a[i] + a[j] + a[k] = 0
047        public static int count(int[] a) {
048                int N = a.length;
049                int cnt = 0;
050                ops = 0;
051                for (int i = 0; i < N; i++) {
052                        for (int j = i+1; j < N; j++) {
053                                for (int k = j+1; k < N; k++) {
054                                        ops += 3;
055                                        if (a[i] + a[j] + a[k] == 0) {
056                                                cnt++;
057                                        }
058                                }
059                        }
060                }
061                return cnt;
062        }
063
064        public static void main(String[] args)  {
065                args = new String[] { "data/100ints.txt" };
066                //        args = new String[] { "data/200ints.txt" };
067                //        args = new String[] { "data/500ints.txt" };
068                //        args = new String[] { "data/1Kints.txt" };
069                //        args = new String[] { "data/2Kints.txt" };
070                //        args = new String[] { "data/4Kints.txt" };
071                //        args = new String[] { "data/8Kints.txt" };
072                int[] a = new In(args[0]).readAllInts();
073
074                //printAll (a);
075
076                Stopwatch timer = new Stopwatch();
077                int cnt = count(a);
078                StdOut.println("elapsed time = " + timer.elapsedTime());
079                StdOut.println(cnt);
080        }
081}