Pair of Roses-Divide and Conquer

#1

Can you please give hint to solve this problem. I am getting stuck while framing the logic.

#2

@vkth
let number to be searched equal x.store the array elements in the map. now iterate over the array
and for each a[i] check if x-a[i] is present. if present so you got one answer and calculate the diff bw
them as we have to minimize the diff and continue the process

#3

example 10 2 6 8 4 and x=10
a[i] = 10 , 10-10 = 0 is not present so continue
a[i] = 2 , 10-2 = 8 is present so var1=2,var2=8 and diff=6
a[i] = 6 , 10-6 = 4 is present and diff = 2 < 6 so var1=4,var 2=6,diff =2
and so on …

#4

i hope your doubt is cleared if yes dont forget to mark it as resolved in my doubts section @vkth

#5

Thank you for this.
Also, is there any other way as well to solve this problem using divide and conquer approach, since it is given in that section?

#6

well can’t think of how it can be done with divide and conquer because there is no point in
sorting the array and then just keep dividing in half and call both sides as in worst case
it will take lot of time .
the method that i suggested you takes o(n) with unordered_map and o(nlogn) with map
@vkth

#7

Okay. Thank you.:slight_smile:

#8

np just mark the doubt as resoved :smiley: