4 Answers

6 votes
6 votes
Let us consider the array is sorted in increasing Order.
The sum of last two elements is maximum.

Example.
50 70 71 100 200 250
Sum of last two elements 200 +250 = 450.
There is no any other pair of elements(a,b), whose sum is > 450 So a+b<450

So we can say if sum of last two elements is not more than 1000 , there is no pair of elements whose sum is >1000.

otherwise we can say there is a pair of elements (a,b)  where SUM(a,b)>1000

Example.
50 70 71 100 200 950
Sum of last two elements 200 +950 = 1150.

200,950 is a pair of two elements whose sum is >1000.

Let us consider the array is sorted in decreasing Order. The sum of first two elements is maximum.

Applying the Same logic, we get the pair of elements.

Time Complexity = Accessing first two elements(a,b) + Add them + Check SUM(a,b) >1000 +

                           Accessing Last two elements(d,e) + Add them + Check SUM(d,e) >1000

Time Complexity = O(1).
Correct me if I am wrong.
0 votes
0 votes
three approaches for this..

Either follow linear search required O(n^2)

Using binary search which will take O(nlogn)

Since the elements are sorted you can put last two elements nd add to check the conditions requires O(1)
0 votes
0 votes
if we use linear search it takes O(n^2)

let us assume array[a b c]

at first a checks with the b and then c and then d

similarly b and c do the same

if we use binary then it takes nlogn

greedy algorithm gives a better result than these two

tc is just O(1)

Related questions

0 votes
0 votes
1 answer
1
Sabir Khan asked Aug 8, 2018
1,056 views
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is(A) (n)(B) (logn)(C) (log*n)(D) (1)
4 votes
4 votes
1 answer
2
Aghori asked Nov 5, 2017
1,162 views
There are two sorted list each of length $n$. An element to be searched in the both the lists. The lists are mutually exclusive. The maximum number of comparisons require...
11 votes
11 votes
2 answers
3
Shubhanshu asked Jun 5, 2017
11,044 views
The average successful search time taken by binary search on a sorted array of $10$ items?$2.6$$2.7$$2.8$$2.9$Answer is $2.9$My doubt:- But when I am using $log_2n$ for $...
10 votes
10 votes
3 answers
4
Chandramani Adil asked Aug 16, 2017
1,466 views
Suppose the first step in binary search algorithm is changed to M = (9L+R)/10, we know that the complexity of binary search is log(n). What will be the complexity of modi...