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 <[email protected]> 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 <[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.
