The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
109 views

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!

asked in Study Resources by (29 points) | 109 views

1 Answer

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

answered by Junior (571 points)
selected by

Related questions

+1 vote
1 answer
2
0 votes
1 answer
6
0 votes
1 answer
7
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,808 questions
54,481 answers
188,249 comments
74,526 users