GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
214 views

Loading Question

asked in Algorithms by Boss (7.3k points)   | 214 views
dived and conquer . sort input in O(nlogn ) them for evry element aplly binary search.
Sir i dont think we can sort. Bcoz if array contains 5,4,10. And if k=1, then we will get true if we apply sort, but in actual we should get false.bcoz here j<i
@Rahul, while you are sorting the input array, you sort the indices array as well. Then after sorting, when you are comparing the values, compare their indices also. Not a big deal, right?  So (B) can be answer. But if its sorting like heap-sort, its not divide-conquer.
I am not getting how we can use sort for this problem, consider the example given by me in above comment
Lets take your example.
Sorted elements: 4 5 10
Sorted indices: 1 0 2

Now, for each element(say 1st element), if you want to find other element(say 2nd element)  such that difference between these two elements is 'k', then 2nd element is max 'k' positions far from 1st element.

Now, apply binary search on these 'k' elements.

So, I think it would be n.log(n) +  (n/2).log(k)  = n.log(n) + n.log(n) = n.log(n) .......since 'k' can be much larger than 'n'
Yeha nice explanation. But then we will need extra space complexity for indices right??? And i want to know why it cant be done by dynamic programming??
In dynamic programming, we go on solving small problems of the main problem and then use results of these small problems in solving next big problem.

e.g matrix multiplication   M1 * M2 * M3 * M4

By dynamic, you consider first multiplications of 2 matices, then store the results.

Then for finding result for multiplication of3 matrices, you use result obtained for multiplication of 2 matrices.

 

==============================

For above problem, there is no such structure.
Got it. Thanks.

1 Answer

+1 vote
Best answer
@Rahul. Ihave updated my answer. It wont be n.log(n).log(n).  It is n.log(n)
answered by Veteran (14.7k points)  
selected by
Top Users Feb 2017
  1. Arjun

    5288 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2378 Points

  6. sriv_shubham

    2308 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1690 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,860 questions
26,010 answers
59,673 comments
22,113 users