The Gateway to Computer Science Excellence

4 Answers

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

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

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.
by Active (4.7k points)
Yes you are right, I think the question is not properly formed. To find 2 numbers whose addition is > 1000 does not need any search, we can directly find it in last two elements, add them and see if that satisfies the condition. So based on the given question, O(1).
Yes we can directly find  by adding last two elements and see if that satisfies the condition.

But question is that how it can b solved by Binary Search?
We search element when we do not know the position. But here we already know that (if exists) it will definitely be the last two elements. Now you can use binary search to find the last and second last element which will cost you O(log n). if they ask you that a+b = 1000 then using binary search makes sense.
Do we really need binary search??
I think No.
We can get first and last two elements by array indices.
No he is asking that if we use binary search what will happen. Yes definitely we do not need Binary search because it's not helping. But if they would have asked a+b = 1000 then binary search would be useful.
If it is asked a+b=1000, then Greedy Algorithm can be useful cuz it will take O(n) while binary search it will take O(n logn).
Can you please tell me how you can use greedy here with O(n) time?
we will take 1st element of array 'a' and last element 'b' then


{ if(a+b)<1000



   b--; }

return (a,b)

There will be (n-1) comparison i.e. equal to O(n).
0 votes
If we use binary search then time complexity is nlogn... Linear search n square
by (437 points)
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)
by Active (3.5k points)
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)
by (437 points)

Related questions

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
50,666 questions
56,167 answers
93,990 users