ok got it ..thanks for resolving queries :) :)
On Wed, Feb 22, 2012 at 11:10 AM, sunny agrawal <sunny816.i...@gmail.com>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 <atul.87fri...@gmail.com>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
>> <sunny816.i...@gmail.com>wrote:
>>
>>> Yes, read my first post
>>>
>>>
>>> On Wed, Feb 22, 2012 at 10:19 AM, atul anand <atul.87fri...@gmail.com>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 <sunny816.i...@gmail.com
>>>> > 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
>>>>> <atul.87fri...@gmail.com>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 <
>>>>>> sunny816.i...@gmail.com> 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 <sinv...@gmail.com> 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 <
>>>>>>>> sunny816.i...@gmail.com> 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 <sinv...@gmail.com> 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 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.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> 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 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.
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> 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 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.
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> 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 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.
>>>>
>>>
>>>
>>>
>>> --
>>> 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 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.
>>
>
>
>
> --
> 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 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.
