I got an approach, although it is not exactly O( size_of_array ), it will solve your problem in linear time.
arr [ 6, 3, 2, 1, 8]
k = 8
Perform traversal on the array to find out the maximum element.
max = 8
Now make an auxiliary array, say "temp" of size = max+1 = 8+1 = 9 (Indices 0 to 8).
Initialize all elements of temp with -1.
Again perform traversal on 'arr', and for each element 'x' in 'arr' do:
temp[x] = index_of_x_in_arr (as highlighted)
Now, the main searching starts.
Traverse each element of arr and for each element (i = 0 to 4), find 'diff' as:
diff = k - arr [i]
Then check,
(if temp[diff] != -1)
FALSE, means the difference exists in 'arr' at location 'temp[diff]'.
TRUE, means the difference doesn't exist. Then, Just iterate through the loop.
In this case,
for i = 0
diff = 8 - arr [0] = 8 - 6 = 2
And,
temp [diff] = temp [2] = 2 (Not equal to -1)
Thus, temp[diff] exists at location 2 in arr.
Finally, just return the positions 'i' and 'temp[diff]' (i=0 and temp[diff] = 2 in this case).
Time complexity = O(n + max)
//Source Code
#include <stdio.h>
#include<conio.h>
void main ()
{
int arr[] = { 6, 3, 2, 1, 8};
int temp[100];
int k = 8, max, i, diff;
max = arr[0];
//finding maximum element in arr
for (i = 0; i < 5; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
//initializing temp to -1
for (i = 0; i < max; i++)
{
temp[i] = -1;
}
//mapping indices of elements in arr to temp
for (i = 0; i < 5; i++)
{
temp[arr[i]] = i;
}
//performing search
for (i = 0; i < 5; i++)
{
diff = (k - arr[i]);
if(temp[diff] != -1){
break;
}
}
printf("Elements are found at indices %d and %d", i, temp[diff]);
}