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

Loading Question

asked in Algorithms by Loyal (4.8k points)   | 191 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 (11.3k points)  
selected by
Top Users Jan 2017
  1. Debashish Deka

    9614 Points

  2. sudsho

    5554 Points

  3. Habibkhan

    4878 Points

  4. Bikram

    4774 Points

  5. Vijay Thakur

    4498 Points

  6. Arjun

    4408 Points

  7. saurabh rai

    4236 Points

  8. Sushant Gokhale

    4112 Points

  9. Kapil

    3828 Points

  10. santhoshdevulapally

    3808 Points

Monthly Topper: Rs. 500 gift card

19,371 questions
24,203 answers
53,828 comments
20,368 users