CareerCup

what does it mean by "add to a constant C"? What I got is take sum of any two elements of array and that sum will be always constant. If it is so, then all the array elements must be equal. You can easily check the equality of all array elements by taking the 1st element and comparing it with the rest n-1 elements in O(n) time.

Sort the array first and then :

int[] a = {2,5,12,15,17};
i=0;j=a.length-1;
while(i<j){
if( a[i] + a[j] > C )
j--;
else if ( a[i] + a[j] < C )
i++;
else print a[i],a[j];
}
}

for every number in the array,Suppose the number is x,put the C-x as the index in the Hash table,so when carray on ,check whether the number you are dealing in the hash table if it is there then the function should return true.

How about first subtracting every elements of the array by C/2. Then insert the new array into a hash table using the abs value of each elements. If two numbers are hashed to the same place and they have opposite signs, we found the result.

Let the given array be "elements". Let the length of the array be 'N'. Create another array "check" having C+1 elements initialized to 0.

// Initialize "check" in O(N).
// Also subtract individual "elements" in O(N).

for(i=0; i<N;, i++)
{
if (elements[i]<=C)
{
check[elements[i]] = 1;
elements[i] = C - elements[i];
}
}

//Check for the presence C-"elements" using "check" and the modified "elements"
// Again being done in O(N)

for(i=0; i<N;, i++)
{
if (elements[i]<=C)
if (check[elements[i]] == 1)
// The pair is (elements[i],C-elements[i])
}

All the numbers in "elements" are assumed to be greater than or equal to 0 and C is assumed to be +ve. Note that the above algorithm can be used only if we want 2 positive numbers adding up to C. Even addition of (C+1, -1) can give a result C. However, detection of such pairs using the above methodology would require an unbounded array "check" and so the above method cannot be used.

void addsToC(int a[], int c) {
    map<int, int> map;
    for (int i = 0; i < N; ++i) {
        if (map[c - a[i]]) return true;
        map[a[i]] = c - a[i];
    }
    return false;
}

:P