477 views
0 votes
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!

1 Answer

Best answer
2 votes
2 votes

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

selected by

Related questions

0 votes
0 votes
1 answer
1
saba780 asked Apr 26, 2022
884 views
simplify the following logic functionf(ABC)USING k-MAP f(ABC)=(A+B+C') .(A+B'+C')
8 votes
8 votes
2 answers
3