The Gateway to Computer Science Excellence

0 votes

I'm facing a problem these days, the question is saying the following: " Imagine we are having an array of positive integers called (a) and a variable called (k). Among this integers, we are looking for two numbers such that the sum of these two would be the (k). we are in need of designing such algorithm with complexity O(n) that prints out the locations of this two number(if exist)."

for example: **a[6,3,2, 1, 8] ----- n=5 ----- k=8 ------ numbers: 6,2**

in this case what would be the designing of the algorithm?

Thank you all for your efforts, they worth a lot!

+2 votes

Best answer

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

}

52,218 questions

59,888 answers

201,081 comments

118,127 users