CODEWITHSUNDEEP
algorithm
Sharma Shweta
Sharma Shweta

Reputation: 11

Algorithm for- given a set S of n integers and another integer x, determine whether or not there exist two elements in S whose sum is exactly x

Describe an algorithm where , given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x. Please let me know if my algorithm is correct or what modification I need to do? Algorithm:

Algo(i,j,k,S)
    for (j = 1 to S.length - 1 , i++ )
       for (i= j+1 to S.length)
        A[k] = A[j] + A[i]
        if A[k] = x
          return A[i], A[j]
        else j++

Upvotes: 1

Views: 3392

Answers (3)

shA.t
shA.t

Reputation: 16968

I think you need some standards:

1) Add a number before any row, for referring them in future easily.
2) When you use a type of statement formatting keep that formatting:

 for (j = 1   to S.length - 1 , i++ )
 for (i = j+1 to S.length     , ??? )

3) When you need some variables, declare all somewhere: A[], k.

Well, this can be a better one:

0) Start [Algo(i, j, S[], x)] 'i, j are local & S[], x are inputs
1) for (j = 1 to S.length - 1, j++ )
1.1) for (i = j + 1 to S.length, i++ )
1.1.1) if (x = S[j] + S[i])
1.1.1.1) return 'at least one match', S[i], s[j]
2) return 'No match'
3) End

Upvotes: 0

gnasher729
gnasher729

Reputation: 52632

O (n) average time and faster if the array is large and there are many solutions: Start with a set containing the first array element A [0]. Then for i = 1 to (number of elements - 1) check whether x - A [i] is in the set and exit if it is, then add A [i] to the set.

For an array in random order with k solutions, this would be O (N * min (1, 1/sqrt (k)). Thanks to Amit for suggesting the set in the first place.

And if we are looking for multiple values x, we would take advantage of the fact that we already added many values to the set. If we didn't find a solution for one x, and then another x has k solutions, we'd be down to O (N / k) for that x.

Upvotes: 0

amit
amit

Reputation: 178521

Your algorithm has small issues with your algrotihm is -

  • Where did k came from? The index of..?
  • What is x? It is missing as argument
  • Why i and j are arguments?
  • Why do you increase j in i's loop and i in j's loop?
  • You also seem to modify the array as you go, which will yield wrong result

It should be modified to address these issues, something like:

Algo(S,x)
    for (i = 1 to S.length - 1 , i++ )
       for (j= i+1 to S.length)
        t = S[j] + S[i]
        if t = x
          return S[i], S[j]
        else j++

Other than it, your algorithm seems correct and the approach is basically a brute force - you check all pairs, so if such a pair exist, you will definetly find it. However, your approach is inefficient, it runs in O(n^2) time.

This problem can be solved in more efficient ways:

  1. O(nlogn) time (and little extra space) by sorting, and iterating the array, for each element x while iterating, binary search for S-x, if found - the answer is these elements.
  2. O(n) average time + space: store all elements in a hash-set, then iterate the array, and for each element x, search if S-x is in the set or not. If duplicates are allowed in the array, store as a hash-map, and ensure you don't return the same index twice.

Upvotes: 2

Related Questions