Question

Data Structure in Java

The following java method counts how many triples of integers in an array of n distinct integers sum to zero.

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

For example: the following list

[8, -12, 9, 2, 4, -9, -2, 5]

has two triples that sim to zero: (8, -12, 4) and (4, -9, 5).

The problem here is that this is a bad solution to solve the problem and it takes Big O(n^3).

Find another solution to the problem that takes less than O(n^3) of time complexity

Hint 1: Sort the array first (use Java’s built-in Arrays.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]).

Answer 1

Please find your solution below and if doubt comment and do upvote.

CODE:

import java.util.Arrays;
public class Main
{
    //time complexity is O(N^2)
    public static int counts(int[] a) {
    int n = a.length;
    int count = 0;
    //sort the array
    Arrays.sort(a);
    //using loop tarverse the array
    for (int i = 0; i < n-1; i++) {
      int left=i+1;
      int right=n-1;
      int value=a[i];
      while(left<right)
      {
          //if sum equals 0 then increase count
          if((value+a[left]+a[right])==0){
              count++;
              left++;
              right--;
          }
          else if ((value+a[left]+a[right])<0)//else increase left index
          left++;
          else 
          right--;//decrease right index
      }
   }
   return count;//return count
}
        public static void main(String[] args) {
                int a[]={8, -12, 9, 2, 4, -9, -2, 5};
                System.out.println(counts(a));
                
        }
}

OUTPUT: