-->

Pair of array elements whose Sum equal to Target Integer

Posted by Admin on
Given a source array of integers with possible duplicates and a target integer, write algorithm to find out 2 numbers in source array whose sum is equal to target integer.
for eg: 


If we have an array a[]={4,1,2,7,9,3}; and target intgere equal to 5
then the pair will be {4,1},{2,3}
hence number of pair will be 2.

Method 1: (Brute force) 
By applying two nested for loop .


for(int i=0;i<n ;i++)
{
for(int j=0;j<n;j++)
{
if(a[i]+a[j]==tagertIngeter && i!=j)
{
count ++;
}
j++;
}
i++;
}
    
Time Complexity: O(n*n).

Method 2: (Using Sorting )

SumToTarget (a[], ar_size, sum)
1) Sort the array in ascending order using merge sort for low complexity.
2) Initialize two index variables to find the candidate
   elements in the sorted array.
       (a) Initialize first to the leftmost index: first_index = 0
       (b) Initialize second  the rightmost index:  last_index = ar_size-1
3) Loop while first_index < last_index.
       (a) If (A[first_index] + A[last_index] == sum)  then return 1
       (b) Else if( A[first_index] + A[last_index] <  sum )  then last_index++
       (c) Else first_index--   
4) If no candidates in whole array - return 0

Implementation :
import java.util.*;
import java.lang.*;
 
class Main
{
        public static void main (String[] args) throws java.lang.Exception
        {
        int a[]={4,1,2,7,9,3};
        int length=a.length;
        length--;
        mergesort(a,0,length);
        if(SumToTarget(a,0,length,4)==1)
        System.out.println("Duplicates exist in the array");
        else 
        System.out.println("Duplicates does not exist in the array");
        }   
        
    /* Function to check whether the duplicates whose sum equal to target num exist or not */
    public static int  SumToTarget(int a[],int start,int last , int num)
    {
        int first_index=start;
        int last_index=last;
       /*if first_index becomes greater than last_index it means duplicates does not exist */
        while(first_index<last_index)
        {
        /* if sum of dupliactes is equal to required sum it means duplicates are present hence returning 1  */
        if((a[first_index]+a[last_index])==num )
            {
                 System.out.println("Two numbers are:->"+a[first_index]+" "+a[last_index]);
                 return 1;
                 
            }
        /*if sum of two number is greater than the required sum then the last_index will be decreased*/
        else if((a[first_index]+a[last_index])>num)
            {
                last_index--;
            }
        /*if sum of two number is less than the required sum then the first_index will be increased*/    
        else if((a[first_index]+a[last_index])<num)
            {
                first_index++;
            }
        }
        
     /*program will reach here only if there no duplicates equal to sum consequently will return 0 */
           return 0;
    }
 
    public static void  mergesort(int a[],int start,int last)
    {
        if(start<last)
        {
            int mid=(start+last)/2;
            mergesort(a,start,mid);
            mergesort(a,mid+1,last);
            merge(a,start,last,mid);
        }
    }
    public static void merge(int a[],int start ,int last,int mid )
    {
        int j,k,l;
        int c[]=new int[a.length];
        j=start;
        k=start;
        l=mid+1;
        while(j<=mid && l<=last )
        {
            if(a[j]<a[l])
            {
                c[k]=a[j];
                k++;
                j++;
            }
            else
            {
                c[k]=a[l];
                k++;
                l++;
            }
        }
        while(j<=mid)
        {
            c[k]=a[j];
            k++;
            j++;
        }
        while(l<=last)
        {
        c[k]=a[l];
        k++;
        l++;
        }
       
        for(int i=start;i<=k-1;i++)
        {
            a[i]=c[i];
        }
    }
} 

Analysis:-

As we know that time complexity of mergesort is O(nlogn) and time complexity of sumToTarget function is O(n) resulting:-
O(nlogn)+O(n)=O(nlogn)
since according to the rule bigger time complexity is considered .

Time Complexity :- O(n*logn)

Please comment if you find any mistake :

No comments:

Post a Comment