finding pair of an element in the array such that diff will be given no.

Question

We are given a sequence of $n$ positive numbers $a_{1}, a_{2}, \ldots, a_{n}$ and a fixed number $k>0$. We want to find a pair of numbers $a_{i}$ and $a_{j}$ such that $j>i$ and $a_{j}-a_{i}=k$. If there is no such pair we want to output "false". This can be solved easily in big-theta( $\mathrm{n}^{2}$ ) time by examining all pairs of numbers. If want to devise an algorithm of $O(n \log n)$ then which method you will follow to solve this problem?
(A) Dynamic programming
(C) Either ' a ' or ' b '
(B) Divide-and-conquer
(D) None of the these

Comments

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.

Answer 1

@Rahul. Ihave updated my answer. It wont be n.log(n).log(n).  It is n.log(n)

Answer 2

what i think the answer should be B as i am using this method in the sorting technique and also in the search approach.. well someone can do it using A so it can be the answer. what i tried is this.

sort elements in nlogn time

now pic the middle element and subtract from the last one. ( as the difference should be positive , if negative pic the starting element)

** further i m describing for positive difference. the algorithm can be ,modified for negative as well .

now subtract the mid and last element . if the diffrence we get is more than the difference we need. then we will set mid as the lower and again calculate the mid , as by moving toward more big numbers only the difference will decrease.
like here

take array

6  4 9  2  1

sort .

1 2  4  6  9  .

suppose i want 3 as a difference, then

picking middle element i.e =4. that is 9-4 = 5. . so as the answer is greter than what we ned then we have to move toward 9 because then only we can decrease our answer, if i move toward 1 the difference will increase. so in this way i can use the binary search type method to get . make such n iterations. each time leaving the highest element that has been examined.

time complexity . = (nlogn)+ n*logn. = (nlogn) .

i don't think repeating subproblems are there , and divide and conquer , as used . may be the answer

Comments

@Tendua sir,

for ex if series like(after sorting) 1  5  8  14   16 and diff=7. then

mid=8 ,last-mid=16-8=8  then according to you we move towards 16..but i think we have to move towards 1.

am i wrong?

---

ohh i missed this case. well i think then we can make n such iterations. each time leaving the highest number. complexity will still the same . i made my example taking the last element as reference, and it should change , i thing now it should work.

---

why will u get negative when it is already sorted and and subtracting aj from ai will always give u positive result only

---

And I guess you can take  the difference of both the mid and last and mid and first and then check the range between the calculated differences and accordingly approach either towards the left or towards the right .