Thursday, May 30, 2013

Find two elements in array having sum equal to given element

We can use insertion sort method to find the two element from the array having sum same as given element. Method FindSum displays two elements from array having sum same as given element.

void FindSum( int * a, int size, int Sum)
{
    int firstNum = 0, secondNum = -1;
    for(; firstNum < size; firstNum++)
    {
        int sercahKey = Sum - a[firstNum];
        for( int i = firstNum + 1; i < size; i++)
        {
            if( sercahKey == a[i] )
            {
                secondNum = i;
                break;
            }
        }
        if( secondNum != -1 )
            break;
    }
    if( secondNum == -1 )
        cout << "Could not found two number having sum " << Sum << endl;
    else
        cout << "found two number having sum [" << Sum  << "] as [ " << a[firstNum] << "] and [" << a[secondNum] << "]."  << endl;

}


The above method requires o(n2) time complexity. Using map the time complexity can be reduced to o(n) as shown in below method.


void FindPairMatchingSum(int * arr,  int size, int sum)
{

    map<int, int> mapOfArray;
    for (int i = 0; i < size; i++)
    {
        mapOfArray.insert(make_pair(arr[i], i));
    }

    for (int  i = 0; i <size; i++)
    {
        int key = sum - arr[i];
        map<int, int>::const_iterator kit = mapOfArray.find(key);
        if (kit != mapOfArray.end())
        {
            cout << "Found Pair at index : " << i  << "  & " << kit->second;
            break;
        }
    }
}

No comments:

Post a Comment