324 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
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.

@Rahul. Ihave updated my answer. It wont be n.log(n).log(n).  It is n.log(n)
answered by Veteran (18k points) 7 20 76
selected

+1 vote
1
+1 vote
2