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