Searching for a sum in an array

Question

I have a method which counts how many sums of 3 elements,which are equal to 0, does the array contains. I need help finding the way to stop counting the same triplets in the loop. For instance, 1 + 3 - 4 = 0, but also 3 - 4 +1 = 0.Here is the method:

private static int counter(int A[])
    {   
         int sum;
         int e = A.length;
         int count = 0;
         for (int i=0; i<e; i++)
         {
             for (int j=i+1; j<e; j++)
             {
                 sum=A[i]+A[j];
                 if(binarySearch(A,sum))
                 {
                      count++;
                 }
             }  
         }
         return count;

edit: I have to use the Binary Search (the array is sorted). Here is the binarySearch code:

   private static boolean binarySearch(int A[],int y)
    {   
        y=-y;
        int max = A.length-1;
        int min = 0;
        int mid;
        while (max>=min)
        {      
            mid = (max+min)/2;
            if (y==A[mid])
            {
                return true;
            }   
            if (y<A[mid]) 
            {
                max=mid-1;
            }
            else
            {
                min=mid+1;
            }
        }
        return false;

Answer 1

you can use a assisted Array,stored the flag that indicate if the element is used; Here is the code:

private static int counter(int A[])
{   
     int sum;
     int e = A.length;
     int count = 0;
     // assisted flag array
     List<Boolean> flagList = new ArrayList<Boolean>(e);
     for (int k = 0; k < e; k++) {
        flagList.add(k, false);// initialization
     }
     for (int i=0; i<e; i++)
     {
         for (int j=i+1; j<e; j++)
         {
             sum=A[i]+A[j];
             // if element used, no count
             if(binarySearch(A,sum)&& !flagList.get(i)&& !flagList.get(j))
             {
                  count++;
                  flagList.set(i, true);
                  flagList.set(j, true);
             }
         }  
     }
     return count;

Answer 2

Here is my solution assuming the array is sorted and there are no repeated elements, I used the binary search function you provided. Could the input array contain repeated elements? Could you provide some test cases?

In order to not counting the same triplets in the loop, we should have a way of inspecting repeated elements, the main idea that I used here is to have a list of int[] arrays saving the sorted integers of {A[i],A[j],-sum}.Then in each iteration I compare new A[i] and A[j] to the records in the list, thus eliminating repeated ones.

    private static int counter(int A[]){   
     int sum;
     int e = A.length;
     int count = 0;
     List<int[]> elements = new ArrayList<>();
     boolean mark = false;
     for (int i=0; i<e; i++)
     {
         for (int j=i+1; j<e; j++)
         {
             sum=A[i]+A[j];

             if (-sum == binarySearch(A,sum)){
                 int[] sort = {A[i],A[j],-sum};
                 if(-sum == A[i] || -sum == A[j]){
                     continue;
                 }else{
                     Arrays.sort(sort);
                     //System.out.println("sort" + sort[0] + " " + sort[1]+ " " + sort[2]);
                     for (int[] element : elements) {
                         if((element[0] == sort[0] && element[1] == sort[1]) && element[2] == sort[2])
                             mark = true;
                     }
                     if(mark){
                         mark = false;
                         continue;
                     }else{
                         count++;
                         elements.add(sort);
                         //System.out.println("Else sort" + sort[0] + " " + sort[1]);
                     }
                 }
             }  
         }  
     }
     return count;
}

Answer 3

You can avoid counting different triplets by making one assumption that we need to look for the triplets (x,y,z) with x < y < z and A[x] + A[y] + A[z] == 0.

So what you need to do is to modify the binarySearch function to return the number of index that greater than y and has A[z] == -(A[x] + A[y])

private static int binarySearch(int A[],int y, int index)
    {   
        y=-y;
        int max = A.length-1;
        int min = index + 1;
        int mid;
        int start = A.length;
        int end = 0;
        while (max>=min)
        {      
            mid = (max+min)/2;
            if (y==A[mid])
            {
                start = Math.min(start, mid);
                max = mid - 1;
            } else  
            if (y<A[mid]) 
            {
                max=mid-1;
            }
            else
            {
                min=mid+1;
            }
        }
        int max = A.length - 1;
        int min = index + 1;
        while (max>=min)
        {      
            mid = (max+min)/2;
            if (y==A[mid])
            {
                end = Math.max(end, mid);
                min= mid + 1;
            } else if (y<A[mid]) 
            {
                max=mid-1;
            }
            else
            {
                min=mid+1;
            }
        }
        if(start <= end) 
           return end - start + 1;
        return 0;
}

So the new function binarySearch will return the total number of index that greater than index and has value equals to y.

So the rest of the job is to count the answer

private static int counter(int A[])
{   
     int sum;
     int e = A.length;
     int count = 0;
     for (int i=0; i<e; i++)
     {
         for (int j=i+1; j<e; j++)
         {
             sum=A[i]+A[j];
             count += binarySearch(A,sum, j);

         }  
     }
     return count;
}

Notice how I used two binary search to find the starting and the ending index of all values greater than y!

Answer 4

To solve problem with binary search
Your code was almost correct. all you needed to do was just to replace

if (sum == binarySearch(A,sum)) {

with this

if (binarySearch(A,sum)) {

I am assuming that your binarySearch(A, sum) method will return true if it will found sum in A array else false

private static int counter(int A[]) {   
    int sum;
    int e = A.length;
    int count = 0;
    for (int i=0; i<e; i++) {
        for (int j=i+1; j<e; j++) {
            sum=A[i]+A[j];
            if (binarySearch(A,sum)) {
                count++;
            }  
        }  
    }
    return count;
}

Answer 5

private static int counter(int ints[]) {
  int count = 0;
  for (int i = 0; i < ints.length; i++) {
    for (int j = 0; j < ints.length; j++) {
      if (i == j) {
        // cannot sum with itself.
        continue;
      }
      for (int k = 0; k < ints.length; k++) {
        if (k == j) {
          // cannot sum with itself.
          continue;
        }

        if ((ints[i] + ints[j] + ints[k]) == 0) {
          count++;
        }
      }
    }
  }

  return count;
}

Answer 6

private static int counter(int A[]) {
    int e = A.length;
    int count = 0;
    for (int i = 0; i < e; i++) {
        for (int j = 1; (j < e - 1) && (i != j); j++) {
            for (int k = 2; (k < e - 2) && (j != k); k++) {
                if (A[i] + A[j] + A[k] == 0) {
                    count++;
                }
            }
        }
    }
    return count;
}