Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
@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 atul.87fri...@gmail.com wrote:
ok got it ..thanks for resolving queries :) :)
On Wed, Feb 22, 2012 at 11:10 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
*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.comwrote:
/*
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.comwrote:
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.comwrote:
@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 = 3count += 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.comwrote:
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
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
ok got it ..thanks for resolving queries :) :)
On Wed, Feb 22, 2012 at 11:10 AM, sunny agrawal sunny816.i...@gmail.comwrote:
*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.comwrote:
/*
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.comwrote:
Yes, read my first post
On Wed, Feb 22, 2012 at 10:19 AM, atul anand atul.87fri...@gmail.comwrote:
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.comwrote:
@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 = 3count += 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
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
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.comwrote: 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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
if i am getting it right input has only positive number then if k = N (number of elements) , then it would similar to finding kth smallest element in the array. because we can consider each element in the input as a sub array. now if k N , then we need to find (k-N)th smallest element which should be sum two or more elements. On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal sunny816.i...@gmail.comwrote: 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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
can you do it for some example where k N... i am confused On Wed, Feb 22, 2012 at 12:22 AM, atul anand atul.87fri...@gmail.comwrote: if i am getting it right input has only positive number then if k = N (number of elements) , then it would similar to finding kth smallest element in the array. because we can consider each element in the input as a sub array. now if k N , then we need to find (k-N)th smallest element which should be sum two or more elements. On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal sunny816.i...@gmail.comwrote: 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. -- 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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
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 = 3count += 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.comwrote:
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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
great solution :D
thanks.
On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal sunny816.i...@gmail.comwrote:
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 = 3count += 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.comwrote:
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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
@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
contiguous sum (1,2) , (2,3) -- these contiguous sum has already been
counted
so output is 4.
correct me if i am wrong...
On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal sunny816.i...@gmail.comwrote:
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 = 3count += 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.comwrote:
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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
@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.comwrote:
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 = 3count += 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
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
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.comwrote:
@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.comwrote:
@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.comwrote:
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 = 3count += 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
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
Yes, read my first post
On Wed, Feb 22, 2012 at 10:19 AM, atul anand atul.87fri...@gmail.comwrote:
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.comwrote:
@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.comwrote:
@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 = 3count += 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
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
*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.comwrote:
/*
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.comwrote:
Yes, read my first post
On Wed, Feb 22, 2012 at 10:19 AM, atul anand atul.87fri...@gmail.comwrote:
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.comwrote:
@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.comwrote:
@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 = 3count += 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
