Question

An integer x and a sequence b,...b, of integers is given. The problem is to find indices i, j, such that b,+b, = x . Suggest a data structure and/or an algorithm for answering such questions and analyze their complexity. (Try to optimize the asymptotic complexity of your solution.)

Answer 1

Answer:

Algorithm -

1.Firstly, Sort(b)

2.Then, Set i=0,j=n-1,flag=1

3.When, while(i<j)

4.Then, Set if b[i] + b[j] == x

5.Then, flag=0

6.Then, break the following condition.

7.Set if b[i] + b[j] < x //when the following condition is true

8.Then, the value of i increase i=i+1

9.Either, else

10Then, the value of j decrease j=j-1

11.Then, Set if flag == 0

12.And print b[i],b[j]

13.Otherwise else

14. no such pair exists.

Time complexity analysis -

Sort - O(nlogn)

while loop - O(n)

Total - O(nlogn)+O(n) = O(nlogn)

Explanation:

Firstly, sort these sequence(array) of the integers. It takes O(N log N) time if done with the Merge Sort or the Heap Sort or any other sorting the algorithm within less time complexity.

After that, take two indices one at the start and one at the end. Traverse these array from the start to the end based on the sum of the values.