Question

Topic is Big O

Problem 5

Invent a faster solution to the ThreeSum problem. Then determine the number of triples of integers that sum to zero in 8ints.txt.

Hint 1:Sort the array first (use Java’s built-inArrays.sort(int[] a))method to sort the array first.

Hint 2:A pair a[i] and a[j] is part of a triple that sums to zero if and only if the value-(a[i]+ a[j])is in the array (but not a[i] or a[j] ).

-----------------

ThreeSum.java

import java.util.Arrays;

public class ThreeSum {
   public static int count(int[] a) {
      int n = a.length;
      int count = 0;
      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)
                  count++;
            }
         }
      }
      return count;
   }

   public static void main(String[] args) {
      In in = new In("8Kints.txt");
      int[] a = in.readAllInts();

      System.out.println("The original array of ints: " + Arrays.toString(a));

      long startTime = System.currentTimeMillis();
      System.out.println("Count is: " + ThreeSum.count(a));
      long endTime = System.currentTimeMillis();
      long timeElapsed = endTime - startTime;
      System.out.println("Execution time in milliseconds  : " + timeElapsed);
   }
}

---------------

8ints.txt

8
-12
9
2
4
-9
-2
5

------------

Answer 1

Solution :

Simply sort the array.

Assign 'left' the leftmost index and 'right' the rightmost index and start iteration from the 0th index

At every index check for the condition of sum of the elements to be equal to 0, If the sum is 0,increment left and decrement right, else if sum is greater than 0, decrement right else increment index.

Repeat the above steps and update count.

Following is the Java code for same :

import java.util.*;

class ThreeSum {
  public static int count(int[] a) {
    int count=0;
    //sort the array
    Arrays.sort(a);
    for (int i = 0; i < a.length; i++) {
      int left = i + 1;
      int right = a.length - 1;
      while (left < right) {
        if (a[i] == -( a[left] + a[right])) {
          count++;
          left++;
          right--;
        } else if (a[i] + a[left] + a[right] < 0) {
          left++;
        } else {
          right--;
        }
      }
    }
    return count;
  }

   public static void main(String[] args) {
      
      In in = new In("8Kints.txt");
      int[] a = in.readAllInts();

      System.out.println("The original array of ints: " + Arrays.toString(a));

      long startTime = System.currentTimeMillis();
      System.out.println("Count is: " + Main.count(a));
      long endTime = System.currentTimeMillis();
      long timeElapsed = endTime - startTime;
      System.out.println("Execution time in milliseconds  : " + timeElapsed);
   }
}