@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 <[email protected]> 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 <[email protected]> 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 <[email protected]
> >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 <
> [email protected]>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 [email protected].
> > >> To unsubscribe from this group, send email to
> > >> [email protected].
> > >> 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 [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected].
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > Mohit kumar lal
> > rit2009014
> > IIIT ALLAHABAD
> > contact@9454681805
> > [email protected]
> > [email protected]
> > [email protected]http://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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
