@Sunny: A little doubt, how are you making sure that the candidate sum is actually a sum that can be formed by contiguous elements of the array? Can you please explain your algo for this array : 1 , 2 , 99 , 100 , we need the 3rd smallest sum.
On Wed, Feb 22, 2012 at 3:11 PM, atul anand <[email protected]> wrote: > ok got it ..thanks for resolving queries :) :) > > > On Wed, Feb 22, 2012 at 11:10 AM, sunny agrawal > <[email protected]>wrote: > >> *NO, u r getting it wrong* >> *given a value x, we can find how many contiguous sums are lesser than x >> using the above mentioned algorithm in O(N)* >> *so we are searching a x in range 0-S such that, x has exactly k-1 sums >> lesser than x and x is kth* >> * >> * >> *Algorithm: * >> *for >> * >> >> On Wed, Feb 22, 2012 at 10:41 AM, atul anand <[email protected]>wrote: >> >>> /* >>> algo goes as follows >>> *do a binary search in range 0-S*, for each such candidate sum find how >>> many sums are smaller than candidate sum >>> */ >>> do a binary search in range 0-S--> to search what?? >>> acc to the complexity , O(N *log S) it seems that you are searching each >>> element in given input array from range 0-S >>> for given input = 1,2,3,4,5 >>> S= 15 >>> >>> please clarify ..... sorry but i am not getting it ... >>> >>> >>> >>> >>> >>> >>> On Wed, Feb 22, 2012 at 10:25 AM, sunny agrawal <[email protected] >>> > wrote: >>> >>>> Yes, read my first post >>>> >>>> >>>> On Wed, Feb 22, 2012 at 10:19 AM, atul anand >>>> <[email protected]>wrote: >>>> >>>>> sum[0-1] = 3 --> (1,2) >>>>> sum[0-2] = 6 --> (1,2,3) >>>>> sum[1-2] = 5 --> (2,3) >>>>> >>>>> ok...so we can consider 3 , (1,2) as different contiguous. >>>>> >>>>> how did you choose candidate sum for the given input ?? will it not >>>>> add to the complexity >>>>> >>>>> >>>>> On Wed, Feb 22, 2012 at 9:59 AM, sunny agrawal < >>>>> [email protected]> wrote: >>>>> >>>>>> @atul there are 8 sums less than 7 >>>>>> >>>>>> sum[0 - 0] = 1 >>>>>> sum[1-1] = 2 >>>>>> sum[2 - 2] = 3 >>>>>> sum[3-3] = 4 >>>>>> sum[4-4] = 5 >>>>>> sum[0-1] = 3 >>>>>> sum[0-2] = 6 >>>>>> sum[1-2] = 5 >>>>>> >>>>>> contiguous sum (1,2) , (2,3) --> these contiguous sum has already >>>>>> been counted ??? where ? >>>>>> Read problem statement carefully !! >>>>>> >>>>>> >>>>>> On Wed, Feb 22, 2012 at 9:39 AM, atul anand >>>>>> <[email protected]>wrote: >>>>>> >>>>>>> @sunny : before moving to your algorithm , i can see wrong output in >>>>>>> your example:- >>>>>>> >>>>>>> in you example dere are 8 sums less than 7. >>>>>>> but for given input contiguous sum less than 7 are >>>>>>> 1,2,3,4,5 = 4 >>>>>>> so output is 4. >>>>>>> >>>>>>> correct me if i am wrong... >>>>>>> >>>>>>> >>>>>>> On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal < >>>>>>> [email protected]> wrote: >>>>>>> >>>>>>>> we need to find how many sums are less than candidate Sum chosen in >>>>>>>> one iteration of binary search in range 0-S >>>>>>>> To count this, for each i we try to find how many sums ending at i >>>>>>>> are lesser than candidate sum !! >>>>>>>> >>>>>>>> lets say for some i-1 sum[0 - i-1] < candidate sum then we can say >>>>>>>> that i*(i-1)/2 sums are less than candidate sum. >>>>>>>> now lets say after adding a[i] again sum[0 - i] < candidateSum then >>>>>>>> u can add (i+1) to previous count because all sums [0 - i], sum[1 - i], >>>>>>>> ............. sum[i - i] will be lesser than candidate sum >>>>>>>> or if adding a[i] causes sum[0 - i] > candidateSum then u have to >>>>>>>> find a index g such that sum[g - i] < candidate sum, and increase the >>>>>>>> count >>>>>>>> by ((i)-(g) +1). >>>>>>>> >>>>>>>> eg lets say your candidate sum is 7 (for the given >>>>>>>> example{1,2,3,4,5}) k = 3 n = 5 >>>>>>>> initially g = 0 >>>>>>>> sum = 0; >>>>>>>> candidateSum = 7; >>>>>>>> count = 0 >>>>>>>> iteration one: >>>>>>>> sum[0 - 0] = 1 < 7 so count += 0-0+1; >>>>>>>> >>>>>>>> iteration 2 >>>>>>>> sum[0-1] = 3 < 7, count += 1-0+1 >>>>>>>> >>>>>>>> iteration 3 >>>>>>>> sum[0-2] = 6 < 7 count += 2-0+1; >>>>>>>> >>>>>>>> iteration 4 >>>>>>>> sum[0,3] = 10 > 7 so now increment g such that sum[g,i] < 7 >>>>>>>> so g = 3 count += 3-3+1; >>>>>>>> >>>>>>>> iteration 5 >>>>>>>> sum[3 - 4] = 9 > 7 >>>>>>>> new g = 4 count += 4-4+1 >>>>>>>> >>>>>>>> final count = 8, so there are 8 sums less than 7 >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> On Wed, Feb 22, 2012 at 12:16 AM, shady <[email protected]> wrote: >>>>>>>> >>>>>>>>> didn't get you, how to check for subsequences which doesn't start >>>>>>>>> from the beginning ? can you explain for that same example... should >>>>>>>>> we >>>>>>>>> check for all contiguous subsequences of some particular length? >>>>>>>>> >>>>>>>>> >>>>>>>>> On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal < >>>>>>>>> [email protected]> wrote: >>>>>>>>> >>>>>>>>>> i dont know if a better solution exists >>>>>>>>>> but here is one with complexity O(N*logS)... >>>>>>>>>> N = no of elements in array >>>>>>>>>> S = max sum of a subarray that is sum of all the elements as all >>>>>>>>>> are positive >>>>>>>>>> >>>>>>>>>> algo goes as follows >>>>>>>>>> do a binary search in range 0-S, for each such candidate sum find >>>>>>>>>> how many sums are smaller than candidate sum >>>>>>>>>> >>>>>>>>>> there is also need to take care of some cases when there are >>>>>>>>>> exactly k-1 sums less than candidate sum, but there is no contigious >>>>>>>>>> where >>>>>>>>>> sum = candidate sum. >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> On Tue, Feb 21, 2012 at 11:02 PM, shady <[email protected]>wrote: >>>>>>>>>> >>>>>>>>>>> Problem link <http://www.spoj.pl/ABACUS12/status/ABA12E/> >>>>>>>>>>> >>>>>>>>>>> -- >>>>>>>>>>> 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. >>>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> -- >>>>>>>>>> Sunny Aggrawal >>>>>>>>>> B.Tech. V year,CSI >>>>>>>>>> Indian Institute Of Technology,Roorkee >>>>>>>>>> >>>>>>>>>> -- >>>>>>>>>> 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. >>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> -- >>>>>>>> Sunny Aggrawal >>>>>>>> B.Tech. V year,CSI >>>>>>>> Indian Institute Of Technology,Roorkee >>>>>>>> >>>>>>>> -- >>>>>>>> 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. >>>>>>> >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> Sunny Aggrawal >>>>>> B.Tech. V year,CSI >>>>>> Indian Institute Of Technology,Roorkee >>>>>> >>>>>> -- >>>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> Sunny Aggrawal >>>> B.Tech. V year,CSI >>>> Indian Institute Of Technology,Roorkee >>>> >>>> -- >>>> 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. >>> >> >> >> >> -- >> Sunny Aggrawal >> B.Tech. V year,CSI >> Indian Institute Of Technology,Roorkee >> >> -- >> 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. > -- Regards Anurag Atri -- 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.
