sumOfPairs.java

public class sumOfPairs {

	    private static final int MAX = 100000; // Max size of Hashmap
	 
	    static void printpairs(int arr[],int sum)// METHOD 1
	    {
	        // Declares and initializes the whole array as false
	        boolean[] binmap = new boolean[MAX];
	 
	        for (int i=0; i<arr.length; ++i)
	        {
	            int temp = sum-arr[i];
	 
	            // checking for condition
	            if (temp>=0 && binmap[temp])
	            {
	                System.out.println("Pair with given sum " +
	                                    sum + " is (" + arr[i] +
	                                    ", "+temp+")");
	            }
	            binmap[arr[i]] = true;
	        }
	    }
	
	    
	    static boolean hasArrayTwoCandidates(int A[], int arr_size, int sum)		//METHOD2
	    {
	        int l, r;
	       
	        /* Sort the elements */
	        sort(A, 0, arr_size-1);
	       
	        /* Now look for the two candidates 
	           in the sorted array*/
	        l = 0;
	        r = arr_size-1; 
	        while (l < r)
	        {
	             if(A[l] + A[r] == sum)
	             { System.out.println("(" + A[l]+","+A[r]+")");
	            	 return true; 
	             
	             }
	             else if(A[l] + A[r] < sum)
	                  l++;
	             else // A[i] + A[j] > sum
	                  r--;
	        }    
	        return false;
	    }
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int A[] = {1, 4, 45, 6, 10, 8};
        int n = 16;
        printpairs(A,  n);			//METHOD1
        
        if( hasArrayTwoCandidates(A, A.length, n))
            System.out.println("Array has two "+ 
                         "elements with sum 16");
        else
            System.out.println("Array doesn't have "+
                      "two elements with sum 16 ");
	}
	
	
    static int partition(int arr[], int low, int high)
    {
        int pivot = arr[high]; 
         
        // index of smaller element
        int i = (low-1); 
        for (int j=low; j<=high-1; j++)
        {
            // If current element is smaller than or
            // equal to pivot
            if (arr[j] <= pivot)
            {
                i++;
   
                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
   
        // swap arr[i+1] and arr[high]
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;
   
        return i+1;
    }
   
   
    /* The main function that 
       implements QuickSort()
       arr[] --> Array to be sorted,
       low  --> Starting index,
       high  --> Ending index */
    static void sort(int arr[], int low, int high)
    {
        if (low < high)
        {
            /* pi is partitioning index, arr[pi] is 
              now at right place */
            int pi = partition(arr, low, high);
   
            // Recursively sort elements before
            // partition and after partition
            sort(arr, low, pi-1);
            sort(arr, pi+1, high);
        }
    }

}