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.
