Redirected
retagged by
679 views
0 votes
0 votes

retagged by

2 Answers

0 votes
0 votes
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
edited by

Related questions

8 votes
8 votes
2 answers
1
0 votes
0 votes
1 answer
3
dhruba asked Jun 5, 2023
411 views
Consider performing QuickSort on an array of n distinct elements. What is the probability that no comparisons will be made between the smallest and largest element?a. 1/n...
2 votes
2 votes
1 answer
4
yes asked Oct 6, 2015
1,329 views
for example array contain a[1 2 3 3 3 3 3 4 5] then retun(1)