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

Loading Question

asked in Algorithms by Veteran (10.6k points)   | 283 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

+2 votes
Best answer
@Rahul. Ihave updated my answer. It wont be n.log(n).log(n).  It is n.log(n)
answered by Veteran (15.4k points)  
selected by

Related questions



Top Users Aug 2017
  1. ABKUNDAN

    4654 Points

  2. Bikram

    4032 Points

  3. akash.dinkar12

    3136 Points

  4. rahul sharma 5

    2856 Points

  5. manu00x

    2664 Points

  6. makhdoom ghaya

    2380 Points

  7. just_bhavana

    2040 Points

  8. Tesla!

    1756 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1558 Points


24,878 questions
31,952 answers
74,104 comments
30,065 users