@atul ...
Reply 1:
Yes, you are correct.. i missed it... Correct statement is as follows:
12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
i = 3, j = 4
12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
=5 , i = 4, j = 4
-------------------------------------------------------------
Reply 2:
I might be wrong in calculating 12 + 2 = 14.... but i guess you are
not getting my point .... even if 14 is the search element, still the
element smaller than equal to 14 in array B is 10 and not 15...
Hence, the above calculation that you have made are incorrect.
If you look at the problem statement it says that we have to find the
sum which is smaller than equal to X.
Now, if you look ta ur calculations you will see that your 'closest to
X' search space contains elements 13 which is invalid as it is greater
than 12...
Hence, i m re-calculating the values based on the above given
algorithm...
12 + 2 = 14, closest element found = 10 , closest to X = 10 - 2 =
8 , i = 1, j = 3
12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
=12 , i = 2, j = 4
12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
9 , i = 3 , j = 4
12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 =
5 , i = 4 , j = 4
Also, as calculated in the previous post the corner case gives 10 as
the closest to X.
Hence, max of all closest values to X = max { 8, 12, 9, 5, 10 } =
12.
On Dec 1, 2:52 pm, atul anand <atul.87fri...@gmail.com> wrote:
> and you made mistake above in calculating 12 + 2 = *12* , its 14
>
> 12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 = 13 , i
> = 1, j = 4
> 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 , i
> = 2, j = 4
> 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 = 11 , i
> = 3 , j = 4
> 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 = 5 , i
> = 4 , j = 4
>
> out of {10,13,12,11,5 } , element 12 is closest to X ( which is 12) .
> So basically among this we have to find element closest X ( where element <
> = X )
> hence 12 is the answer.
>
>
>
>
>
>
>
> On Thu, Dec 1, 2011 at 3:11 PM, atul anand <atul.87fri...@gmail.com> wrote:
> > @sourabh
>
> > i guess you need to modify this statement :-
>
> > 3) Now for each element B[i][0] , do a (modified) binary *search for
> > the closest value smaller than equal to (X + B[i][0])* in array B[i
> > +1... n][0] ,
> > Say the found index after binary search is j ( which is > i)...
>
> > 12 + 2 = 12 , closest element found = 10 , closest to X = 10 - 2 = 8 , i
> > = 1, j = 3
> > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 , i =
> > 2, j = 4
> > 12 + 6 = 18 , closest element found = *no element found ??? how *
>
> > *Cumulative SUM*
>
> > *i*
>
> > 2
>
> > 0
>
> > 3
>
> > 1
>
> > 6
>
> > 2
>
> > 10
>
> > 3
>
> > *15*
>
> > 4
>
> > for 12 + 6 =18 , closest element less than equal to 18 = 15 (15 < 18 )
> > ..right ??
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
