Pair of roses Problem

#1

I used Divide&Conquer approach in this problem. My code is giving correct answers for the sample test cases given in the question itself and also for some random test cases manually entered through IDE. But, I am getting “wrong answer” upon submission. Here is my code: https://ide.codingblocks.com/s/244262

#2

@a_krisna22
can you please explain me what you are trying to do because i don’t think it is right and it will many case.
because here you also need to take care that the pair you are selecting should be the one with that minimizes the difference between the prices i and j.
for eg:- target is 60, then lets say possible pairs are (20, 40) and (30, 30) then (30, 30) will be your output.

One thing you can do, first sort the array then take every element and find m-arr[i] with the help of binary search (also check that the element found is not same as ‘i’) then considering every such pair compare with previous stored pairs that if the difference between the pairs is less than previous ones or not.

#3

okay, so u are saying I got to simply iterate the sorted array and then check via binary search whether its compliment exists or not and also minimise the difference. Actually,I tried to do everything using divide conquer so as to make the time complexity o((logn)^2), I assumed that the possible combination will always lie close to the mid of the array, and its complement on the other side of array , if I consider the mid point as a dividing point of the array. But, I just realised that this assumption will work for a lot of the cases but not all.

#4

@a_krisna22
So are you able to solve it now?
If not then please ask.
If yes then please mark this doubt as resolved.