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

Loading Question

asked in Algorithms by Veteran (10.5k points)   | 239 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 (15k points)  
selected by

Related questions



Top Users May 2017
  1. akash.dinkar12

    3154 Points

  2. pawan kumarln

    1630 Points

  3. sh!va

    1590 Points

  4. Arjun

    1350 Points

  5. Devshree Dubey

    1246 Points

  6. Angkit

    1044 Points

  7. Debashish Deka

    1022 Points

  8. Bikram

    972 Points

  9. LeenSharma

    836 Points

  10. Prashant.

    692 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. pawan kumarln

    256 Points

  2. Ahwan

    236 Points

  3. jjayantamahata

    114 Points

  4. joshi_nitish

    114 Points

  5. Arnab Bhadra

    94 Points


22,731 questions
29,061 answers
65,101 comments
27,627 users