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]);

}