I am rewriting the algo here in much more readable form :
Given array of integers A,
1) Create an 2-d array B[n][2] of size n*2 such that
a) B[i][0] = sum of all elements from A[0] to A[i],
b) B[i][1] = i
2) Sort array B based on B[i][0] i.e. sort array B[][0] and
correspondingly rearrange elements of array B[][1] ....
3) Now for each element B[i][0] ( till its <= X / 2 ), 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)
4) If B[i][1] < B[j][1] ( if not, then go to step 3), then keep track
of the max no. closest to X ( that is B[i][0] + B[j][0])...
// In case you want to return the indices of the subarray for he max
closest element to X , the have to variable maxi and maxj holding
value B[i][1] and B[j][1] respectively whenever you get a new max. no
closest to X in step 4.
Complexity = N (to create array B) + N log N (to sort) + N log N ( to
solve the problem) = O(n log n)
On Nov 30, 11:21 pm, sourabh <sourabhd2...@gmail.com> wrote:
> First i would like to rectify a editing mistake that is as foolws :
> Say the found index after binary search is j ( which is > i)..
> Now if B[i][1] < B[j][1] then keep track of the max no. closest to X
> ( that is B[i][0] + B[j][0])... // earlier the last text was B[i][1] +
> B[j][1]
>
> Now to clarify your doubts...
>
> 3) Why are u assuming that the array contains positive integers. It
> can as well contain non-positive integers.. hence, array B won't be
> inherently sorted...
>
> 4) As mentioned above, closest element found is B[j][0] which smaller
> than equal to X - B[i][0] ....
> And the closest max value to X is B[i][0] + B[j][0]
>
> Keeping the above 2 points in mind i m re-tracing your example :
>
> let X=12;
> 12 - 2 = 10 , closest element found = 10 , closest to X = 2 + 10 =12
> 12 - 3 = 9 closest element found = 6 , closest to X = 3 + 6 = 9
> 12 - 6 = 6 closest element found = no element found , closest to X =
> 6 + 0 =6
> 12 - 10 = 2 no need to execute this step as 10 > 12 / 2 , because
> 12-10 = 2 which is smaller than 12 and won't lie on the right half...
>
> Hence the max closest to X is 12...and the sub array is A [ B[i]
> [1] ... B[j][1] ]
>
> On Nov 30, 9:39 pm, atul anand <atul.87fri...@gmail.com> wrote:
>
>
>
>
>
>
>
> > @sourabh : please let me know where i am making mistake in understanding
> > your algo:-
>
> > considering your 1st algo:-
>
> > 1) Given array of integers A[n], = {2,1,3,4,5}
>
> > 2) create an array B[n] such that B[i] = sum of all elements from A[1]
> > to A[i], // i guess it should be A[0] to A[i]
>
> > Array B formed :-
>
> > B[]={2,3,6,10,15}
>
> > 3) Now sort array B,
>
> > why you need to sort array B ???, it contain only +ve elements and what you
> > are doing is just the cumulative addition so it will always be sorted.
>
> > 4) for each element B[i] ( smaller that equal to
> > X), do a (modified) binary search for the closest value smaller than
> > equal to (X - B[i]) in array B[i+1... n]
>
> > let X=12;
>
> > 12 - 2 = 10 closest element found = 10
> > 12 - 3 = 9 closest element found = 10
> > 12 - 6 = 6 closest element found = 10
> > 12 - 10 = 2 closest element found = 15
>
> > Answer should be Ans->12, sub-array={3,4,5}
>
> > where i am getting it wrong ???
>
> > On Wed, Nov 30, 2011 at 4:01 PM, sourabh <sourabhd2...@gmail.com> wrote:
> > > Given array of integers A, create an 2-d array B of size n*2 such
> > > that B[i][0] = sum of all elements from A[0] to A[i], B[i][1] = i;Now
> > > sort array B based on B[i][0]..
> > > Now for each element B[i][0] ( till its smaller that equal to X), 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).. Now if
> > > B[i][1] < B[j][1] then keep track of the max no. closest to X ( that
> > > is B[i][1] + B[j][1])... Complexity = N (to create array B) + N log N
> > > (to sort) + N log N ( to solve the problem) = O(n log n)
> > > On Nov 29, 7:13 pm, Mohit kumar lal <kumarmohit...@gmail.com> wrote:
> > > > here it is similar type of question i found on spoj ,it asks only for
> > > > the
> > > > sum
>
> > > >http://www.spoj.pl/problems/HOTELS/
>
> > > > but it is giving TLE in O(n^2)..
>
> > > > On Tue, Nov 29, 2011 at 5:51 PM, Nitin Garg <nitin.garg.i...@gmail.com
> > > >wrote:
>
> > > > > cant think of anything better than O(N^2). Are you sure there exists
> > > such
> > > > > algo?
>
> > > > > On Tue, Nov 29, 2011 at 2:55 AM, Mohit kumar lal <
> > > kumarmohit...@gmail.com>wrote:
>
> > > > >> Given a array of positive integers ,You have to find the largest sum
> > > > >> possible from consecutive sub-array but sum should be less than or
> > > equal to
> > > > >> K and also find that sub-array. Ex- array={2,1,3,4,5} k=12,
> > > > >> ans->12, sub-array={3,4,5}
>
> > > > >> Firstly i tried with brute-force and then i also tried to solve it by
> > > DP
> > > > >> but complexity were same ( O(n^2)) ....so plz try to provide a
> > > solution for
> > > > >> O(nlgn) or O(n).
>
> > > > >> --
> > > > >> Mohit kumar lal
>
> > > > >> IIIT ALLAHABAD
>
> > > > >> --
> > > > >> 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.
>
> > > > > --
> > > > > Nitin Garg
>
> > > > > "Personality can open doors, but only Character can keep them open"
>
> > > > > --
> > > > > 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.
>
> > > > --
> > > > Mohit kumar lal
> > > > rit2009014
> > > > IIIT ALLAHABAD
> > > > contact@9454681805
> > > > kumarmohit...@gmail.com
> > > > mohitkumar...@yahoo.com
> > > > rit2009...@iiita.ac.inhttp://profile.iiita.ac.in/rit2009014
>
> > > --
> > > 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.
--
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.
