Friday, December 27, 2013

Given an array of integers(+ve,-ve,0 or duplicates). Find n print all triplets such that a+b+c=0

/**
   * Given an array of integers(+ve,-ve,0 or duplicates). Find n print all triplets such that a+b+c=0.
   * e.g. Let A = -1 0 9 5 -5 2 3
   * Answer = {0 5 -5} {-5 2 3}.
   * Expected : Time O(n2) Space O(1)
 */
public class Prob3Sum {

    public void find3Sum(int A[]){
        for(int i=0; i<A.length; i++){
            int l = i+1;
            int r = A.length - 1;
            while(l<r){
                if(A[i] + A[l] + A[r] == 0){
                    System.out.println("Sum: " + A[i] + " " + A[l] + " " + A[r]);
                }
                if(A[i] + A[l] + A[r] > 0)
                    r--;
                else
                    l++;
            }
        }
    }
   
    public static void main(String args[]){
        QuickSort sort = new QuickSort();
        sort.A = new int[]{-1, 0, 9, 5, -5, 2, 3};
        sort.quickSort(sort.A, 0, sort.A.length-1);
        sort.printArr();
       
        Prob3Sum ps = new Prob3Sum();
        ps.find3Sum(sort.A);
       
    }
}

#output
Sorted: -5, -1, 0, 2, 3, 5, 9, 
Sum: -5 0 5
Sum: -5 2 3

No comments:

Post a Comment