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