Re: [algogeeks] finding subarray
using extra space of O(n) we can do it in O(n^2) take an array for storing cumulative sums from index i till 0, then from i+1 till n-1 find summing each array value find whether it exists in array. if its so display indexes eg Array: 2,2,13,4,7,3,8,12,9,1,5 i = 3 ^ temp array: 4, 17, 19, 21 finding for cumulative sums from i+1 till i=(any of values in temp array) i = 6 ^ temp array: 8, 11, 18, 22 finding for cumulative sums from i+1 till i=(any of values in temp array) found values from i+1 till i+3 Repeating for every i, surender On Mon, Jan 9, 2012 at 11:22 PM, priyanka jaggi priyankajag...@gmail.comwrote: Given an array (length n), we need to find the subarray (length k) such that the sum of the first j elements of the subarray equals the sum of the remaining (k-j) elements of the subarray. For e.g. Array: 2,2,13,4,7,3,8,12,9,1,5 Output: 4,7,3,8,12,9,1 [4+7+3+8=12+9+1] Could this be done with a complexity better than O(n^3) k is not given . -- 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] Finding subarray
Let there be n elements v1, v2, v3 .. vn
Let S(i,k) mean - Sum k exists in a subset of {v1, v2, v3, ... vi}
At any given time, if solution has not yet been found then :
S(i,k) = S(i-1,k-vi) + vi or no solution exists
We need to find S(n,k)
So in a systematic fashion, solve S(1,1), S(1,2), S(1,3) ... S(1,k) ,
S(2,1), S(2,2), S(2,3), S(2,4) .. S(2,k) , ... S(n,1), S(n,2) ..
S(n,k)
On Wed, Mar 30, 2011 at 2:46 AM, Subhransu
subhransu.panigr...@gmail.com wrote:
set of integers in an array X that the sum equals a given number N
Eg. X = {-1, -3, 5, 13, 2, 24, 9, 3, 3}
Lets say the number 5 which can be formed in the following manner 5= 2 + 3
(the values from array). If there is no match it has to return
invalid numbers.
We also have to see the complexity of the solution.
I thought of one approach but not sure if there is more approach where the
complexity will be minimal.
Lets say sort the array and now take number and find the closest number for
that.
Then in a recursion manner search for another( Lets say number '5', it
search the list and found closest match
will be 3. Then recursively search for 3 now where closest match is 2)
Any algo with better complexity will be appreciated.
Subhransu Panigrahi
Email: subhransu.panigr...@gmail.com
--
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] Finding subarray
myapproach( set S , sum s ) :
Let all elements be set S and we need to find sum , s
1. for each element taken from the set ,e
2. now call the function recursively with myapproach( S - { e } , s - e )
and myapproach( S - {e } , s )
On Mon, Apr 11, 2011 at 3:17 PM, Subhransu subhransu.panigr...@gmail.comwrote:
I didnt get the step 3. Could you please elaborate this(dry run be good to
understand and bringing it for generic solution).
Also how best the complexity will be .
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
On Mon, Apr 11, 2011 at 12:27 AM, ArPiT BhAtNaGaR
arpitbhatnagarm...@gmail.com wrote:
well i hav deviced a approach :
well say we hav sorted array {-1 -3 2 3 3 5 9 13 24}
say we hav to seach 6
take sum of all neg no store it -4 means we can atmost reduce any no
by 4 units means in any case we cant take no greater than 10-4=6 for finding
6.
now locate the upto position just less than we r searching for here 9
now sum up all positive upto 9 3+2+3+3+5 ie 16 now
WE hav 3 sets
(1) negative no sum
(2) postive no less than requred sum
(3) greater no set we can easily check here since only of
this set less than 10 is useful so we hav 9 check for 9 -1 -3 here
we get 6.
either way we hav 16 -4 need some thing done here
NOT PURE SOLN JUST AN IDEA THOUGH GOOD TO BE SHARE
On Thu, Mar 31, 2011 at 1:06 AM, Subhransupanigrahi
subhransu.panigr...@gmail.com wrote:
could you please point to some similar
I just want to validate the approach which I am thinking of.
Sent from my iPhone
On Mar 31, 2011, at 0:59, hammett hamm...@gmail.com wrote:
We did :-) Dynamic programming seems as the best way to approach this
kind of problem.
On Wed, Mar 30, 2011 at 12:56 AM, Subhransu
subhransu.panigr...@gmail.com wrote:
For this X = {-1,4,2,3}
Nearest will be 4 then remain is 1 but the there is no 1 so again in
recursion nearest number is 2 then it search for suitable number where
the
sum is zero so 3 is not suitable then it will pick the next closest
number
to 2 which is one and make it (5= 4 + 2 -1 )
I just propose one approach you guys also can think a better one.
Subhransu Panigrahi
Mobile: +91-9840931538
Email: subhransu.panigr...@gmail.com
On Wed, Mar 30, 2011 at 12:55 PM, Saikat Debnath
crazysai...@gmail.com
wrote:
@ Subhranshu : Your approach will fail for a case let X = {-1,4,2,3}
and
your sum is 5. You will get nearest element 4, but there is no 1 in
the set.
A DP solution will be like this :
Let a[i][j] be the 1 if using the first i elements we can get sum of
j,
and 0 otherwise. Initialise a[0][j] = 0, a[i][0] = 1;
Now a[i][j] = a[i-1][j] | a[i-1][ j - X[i] ], where X[i] is ith
element of
set X.
On Wed, Mar 30, 2011 at 12:35 PM, hammett hamm...@gmail.com wrote:
I'd try a tabular approach. Check dynamic programming. Samples like
LCS may give you a click.
On Tue, Mar 29, 2011 at 11:46 PM, Subhransu
subhransu.panigr...@gmail.com wrote:
set of integers in an array X that the sum equals a given number N
Eg. X = {-1, -3, 5, 13, 2, 24, 9, 3, 3}
Lets say the number 5 which can be formed in the following manner
5= 2
+ 3
(the values from array). If there is no match it has to return
invalid numbers.
We also have to see the complexity of the solution.
I thought of one approach but not sure if there is more approach
where
the
complexity will be minimal.
Lets say sort the array and now take number and find the closest
number
for
that.
Then in a recursion manner search for another( Lets say number '5',
it
search the list and found closest match
will be 3. Then recursively search for 3 now where closest match is
2)
Any algo with better complexity will be appreciated.
Subhransu Panigrahi
Email: subhransu.panigr...@gmail.com
--
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.
--
Cheers,
hammett
http://hammett.castleproject.org/
--
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
Re: [algogeeks] Finding subarray
I didnt get the step 3. Could you please elaborate this(dry run be good to
understand and bringing it for generic solution).
Also how best the complexity will be .
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
On Mon, Apr 11, 2011 at 12:27 AM, ArPiT BhAtNaGaR
arpitbhatnagarm...@gmail.com wrote:
well i hav deviced a approach :
well say we hav sorted array {-1 -3 2 3 3 5 9 13 24}
say we hav to seach 6
take sum of all neg no store it -4 means we can atmost reduce any no
by 4 units means in any case we cant take no greater than 10-4=6 for finding
6.
now locate the upto position just less than we r searching for here 9
now sum up all positive upto 9 3+2+3+3+5 ie 16 now
WE hav 3 sets
(1) negative no sum
(2) postive no less than requred sum
(3) greater no set we can easily check here since only of
this set less than 10 is useful so we hav 9 check for 9 -1 -3 here
we get 6.
either way we hav 16 -4 need some thing done here
NOT PURE SOLN JUST AN IDEA THOUGH GOOD TO BE SHARE
On Thu, Mar 31, 2011 at 1:06 AM, Subhransupanigrahi
subhransu.panigr...@gmail.com wrote:
could you please point to some similar
I just want to validate the approach which I am thinking of.
Sent from my iPhone
On Mar 31, 2011, at 0:59, hammett hamm...@gmail.com wrote:
We did :-) Dynamic programming seems as the best way to approach this
kind of problem.
On Wed, Mar 30, 2011 at 12:56 AM, Subhransu
subhransu.panigr...@gmail.com wrote:
For this X = {-1,4,2,3}
Nearest will be 4 then remain is 1 but the there is no 1 so again in
recursion nearest number is 2 then it search for suitable number where
the
sum is zero so 3 is not suitable then it will pick the next closest
number
to 2 which is one and make it (5= 4 + 2 -1 )
I just propose one approach you guys also can think a better one.
Subhransu Panigrahi
Mobile: +91-9840931538
Email: subhransu.panigr...@gmail.com
On Wed, Mar 30, 2011 at 12:55 PM, Saikat Debnath
crazysai...@gmail.com
wrote:
@ Subhranshu : Your approach will fail for a case let X = {-1,4,2,3}
and
your sum is 5. You will get nearest element 4, but there is no 1 in
the set.
A DP solution will be like this :
Let a[i][j] be the 1 if using the first i elements we can get sum of
j,
and 0 otherwise. Initialise a[0][j] = 0, a[i][0] = 1;
Now a[i][j] = a[i-1][j] | a[i-1][ j - X[i] ], where X[i] is ith
element of
set X.
On Wed, Mar 30, 2011 at 12:35 PM, hammett hamm...@gmail.com wrote:
I'd try a tabular approach. Check dynamic programming. Samples like
LCS may give you a click.
On Tue, Mar 29, 2011 at 11:46 PM, Subhransu
subhransu.panigr...@gmail.com wrote:
set of integers in an array X that the sum equals a given number N
Eg. X = {-1, -3, 5, 13, 2, 24, 9, 3, 3}
Lets say the number 5 which can be formed in the following manner 5=
2
+ 3
(the values from array). If there is no match it has to return
invalid numbers.
We also have to see the complexity of the solution.
I thought of one approach but not sure if there is more approach
where
the
complexity will be minimal.
Lets say sort the array and now take number and find the closest
number
for
that.
Then in a recursion manner search for another( Lets say number '5',
it
search the list and found closest match
will be 3. Then recursively search for 3 now where closest match is
2)
Any algo with better complexity will be appreciated.
Subhransu Panigrahi
Email: subhransu.panigr...@gmail.com
--
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.
--
Cheers,
hammett
http://hammett.castleproject.org/
--
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
Re: [algogeeks] Finding subarray
well i hav deviced a approach :
well say we hav sorted array {-1 -3 2 3 3 5 9 13 24}
say we hav to seach 6
take sum of all neg no store it -4 means we can atmost reduce any no
by 4 units means in any case we cant take no greater than 10-4=6 for finding
6.
now locate the upto position just less than we r searching for here 9
now sum up all positive upto 9 3+2+3+3+5 ie 16 now
WE hav 3 sets
(1) negative no sum
(2) postive no less than requred sum
(3) greater no set we can easily check here since only of this
set less than 10 is useful so we hav 9 check for 9 -1 -3 here we get
6.
either way we hav 16 -4 need some thing done here
NOT PURE SOLN JUST AN IDEA THOUGH GOOD TO BE SHARE
On Thu, Mar 31, 2011 at 1:06 AM, Subhransupanigrahi
subhransu.panigr...@gmail.com wrote:
could you please point to some similar
I just want to validate the approach which I am thinking of.
Sent from my iPhone
On Mar 31, 2011, at 0:59, hammett hamm...@gmail.com wrote:
We did :-) Dynamic programming seems as the best way to approach this
kind of problem.
On Wed, Mar 30, 2011 at 12:56 AM, Subhransu
subhransu.panigr...@gmail.com wrote:
For this X = {-1,4,2,3}
Nearest will be 4 then remain is 1 but the there is no 1 so again in
recursion nearest number is 2 then it search for suitable number where
the
sum is zero so 3 is not suitable then it will pick the next closest
number
to 2 which is one and make it (5= 4 + 2 -1 )
I just propose one approach you guys also can think a better one.
Subhransu Panigrahi
Mobile: +91-9840931538
Email: subhransu.panigr...@gmail.com
On Wed, Mar 30, 2011 at 12:55 PM, Saikat Debnath crazysai...@gmail.com
wrote:
@ Subhranshu : Your approach will fail for a case let X = {-1,4,2,3}
and
your sum is 5. You will get nearest element 4, but there is no 1 in the
set.
A DP solution will be like this :
Let a[i][j] be the 1 if using the first i elements we can get sum of j,
and 0 otherwise. Initialise a[0][j] = 0, a[i][0] = 1;
Now a[i][j] = a[i-1][j] | a[i-1][ j - X[i] ], where X[i] is ith element
of
set X.
On Wed, Mar 30, 2011 at 12:35 PM, hammett hamm...@gmail.com wrote:
I'd try a tabular approach. Check dynamic programming. Samples like
LCS may give you a click.
On Tue, Mar 29, 2011 at 11:46 PM, Subhransu
subhransu.panigr...@gmail.com wrote:
set of integers in an array X that the sum equals a given number N
Eg. X = {-1, -3, 5, 13, 2, 24, 9, 3, 3}
Lets say the number 5 which can be formed in the following manner 5=
2
+ 3
(the values from array). If there is no match it has to return
invalid numbers.
We also have to see the complexity of the solution.
I thought of one approach but not sure if there is more approach
where
the
complexity will be minimal.
Lets say sort the array and now take number and find the closest
number
for
that.
Then in a recursion manner search for another( Lets say number '5',
it
search the list and found closest match
will be 3. Then recursively search for 3 now where closest match is
2)
Any algo with better complexity will be appreciated.
Subhransu Panigrahi
Email: subhransu.panigr...@gmail.com
--
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.
--
Cheers,
hammett
http://hammett.castleproject.org/
--
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.
--
Cheers,
hammett
http://hammett.castleproject.org/
--
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] Finding subarray
I'd try a tabular approach. Check dynamic programming. Samples like
LCS may give you a click.
On Tue, Mar 29, 2011 at 11:46 PM, Subhransu
subhransu.panigr...@gmail.com wrote:
set of integers in an array X that the sum equals a given number N
Eg. X = {-1, -3, 5, 13, 2, 24, 9, 3, 3}
Lets say the number 5 which can be formed in the following manner 5= 2 + 3
(the values from array). If there is no match it has to return
invalid numbers.
We also have to see the complexity of the solution.
I thought of one approach but not sure if there is more approach where the
complexity will be minimal.
Lets say sort the array and now take number and find the closest number for
that.
Then in a recursion manner search for another( Lets say number '5', it
search the list and found closest match
will be 3. Then recursively search for 3 now where closest match is 2)
Any algo with better complexity will be appreciated.
Subhransu Panigrahi
Email: subhransu.panigr...@gmail.com
--
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.
--
Cheers,
hammett
http://hammett.castleproject.org/
--
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] Finding subarray
@ Subhranshu : Your approach will fail for a case let X = {-1,4,2,3} and
your sum is 5. You will get nearest element 4, but there is no 1 in the set.
A DP solution will be like this :
Let a[i][j] be the 1 if using the first i elements we can get sum of j, and
0 otherwise. Initialise a[0][j] = 0, a[i][0] = 1;
Now a[i][j] = a[i-1][j] | a[i-1][ j - X[i] ], where X[i] is ith element of
set X.
On Wed, Mar 30, 2011 at 12:35 PM, hammett hamm...@gmail.com wrote:
I'd try a tabular approach. Check dynamic programming. Samples like
LCS may give you a click.
On Tue, Mar 29, 2011 at 11:46 PM, Subhransu
subhransu.panigr...@gmail.com wrote:
set of integers in an array X that the sum equals a given number N
Eg. X = {-1, -3, 5, 13, 2, 24, 9, 3, 3}
Lets say the number 5 which can be formed in the following manner 5= 2 +
3
(the values from array). If there is no match it has to return
invalid numbers.
We also have to see the complexity of the solution.
I thought of one approach but not sure if there is more approach where
the
complexity will be minimal.
Lets say sort the array and now take number and find the closest number
for
that.
Then in a recursion manner search for another( Lets say number '5', it
search the list and found closest match
will be 3. Then recursively search for 3 now where closest match is 2)
Any algo with better complexity will be appreciated.
Subhransu Panigrahi
Email: subhransu.panigr...@gmail.com
--
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.
--
Cheers,
hammett
http://hammett.castleproject.org/
--
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] Finding subarray
For this X = {-1,4,2,3}
Nearest will be 4 then remain is 1 but the there is no 1 so again in
recursion nearest number is 2 then it search for suitable number where the
sum is zero so 3 is not suitable then it will pick the next closest number
to 2 which is one and make it (5= 4 + 2 -1 )
I just propose one approach you guys also can think a better one.
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
On Wed, Mar 30, 2011 at 12:55 PM, Saikat Debnath crazysai...@gmail.comwrote:
@ Subhranshu : Your approach will fail for a case let X = {-1,4,2,3} and
your sum is 5. You will get nearest element 4, but there is no 1 in the set.
A DP solution will be like this :
Let a[i][j] be the 1 if using the first i elements we can get sum of j, and
0 otherwise. Initialise a[0][j] = 0, a[i][0] = 1;
Now a[i][j] = a[i-1][j] | a[i-1][ j - X[i] ], where X[i] is ith element of
set X.
On Wed, Mar 30, 2011 at 12:35 PM, hammett hamm...@gmail.com wrote:
I'd try a tabular approach. Check dynamic programming. Samples like
LCS may give you a click.
On Tue, Mar 29, 2011 at 11:46 PM, Subhransu
subhransu.panigr...@gmail.com wrote:
set of integers in an array X that the sum equals a given number N
Eg. X = {-1, -3, 5, 13, 2, 24, 9, 3, 3}
Lets say the number 5 which can be formed in the following manner 5= 2 +
3
(the values from array). If there is no match it has to return
invalid numbers.
We also have to see the complexity of the solution.
I thought of one approach but not sure if there is more approach where
the
complexity will be minimal.
Lets say sort the array and now take number and find the closest number
for
that.
Then in a recursion manner search for another( Lets say number '5', it
search the list and found closest match
will be 3. Then recursively search for 3 now where closest match is 2)
Any algo with better complexity will be appreciated.
Subhransu Panigrahi
Email: subhransu.panigr...@gmail.com
--
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.
--
Cheers,
hammett
http://hammett.castleproject.org/
--
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] Finding subarray
We did :-) Dynamic programming seems as the best way to approach this
kind of problem.
On Wed, Mar 30, 2011 at 12:56 AM, Subhransu
subhransu.panigr...@gmail.com wrote:
For this X = {-1,4,2,3}
Nearest will be 4 then remain is 1 but the there is no 1 so again in
recursion nearest number is 2 then it search for suitable number where the
sum is zero so 3 is not suitable then it will pick the next closest number
to 2 which is one and make it (5= 4 + 2 -1 )
I just propose one approach you guys also can think a better one.
Subhransu Panigrahi
Mobile: +91-9840931538
Email: subhransu.panigr...@gmail.com
On Wed, Mar 30, 2011 at 12:55 PM, Saikat Debnath crazysai...@gmail.com
wrote:
@ Subhranshu : Your approach will fail for a case let X = {-1,4,2,3} and
your sum is 5. You will get nearest element 4, but there is no 1 in the set.
A DP solution will be like this :
Let a[i][j] be the 1 if using the first i elements we can get sum of j,
and 0 otherwise. Initialise a[0][j] = 0, a[i][0] = 1;
Now a[i][j] = a[i-1][j] | a[i-1][ j - X[i] ], where X[i] is ith element of
set X.
On Wed, Mar 30, 2011 at 12:35 PM, hammett hamm...@gmail.com wrote:
I'd try a tabular approach. Check dynamic programming. Samples like
LCS may give you a click.
On Tue, Mar 29, 2011 at 11:46 PM, Subhransu
subhransu.panigr...@gmail.com wrote:
set of integers in an array X that the sum equals a given number N
Eg. X = {-1, -3, 5, 13, 2, 24, 9, 3, 3}
Lets say the number 5 which can be formed in the following manner 5= 2
+ 3
(the values from array). If there is no match it has to return
invalid numbers.
We also have to see the complexity of the solution.
I thought of one approach but not sure if there is more approach where
the
complexity will be minimal.
Lets say sort the array and now take number and find the closest number
for
that.
Then in a recursion manner search for another( Lets say number '5', it
search the list and found closest match
will be 3. Then recursively search for 3 now where closest match is 2)
Any algo with better complexity will be appreciated.
Subhransu Panigrahi
Email: subhransu.panigr...@gmail.com
--
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.
--
Cheers,
hammett
http://hammett.castleproject.org/
--
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.
--
Cheers,
hammett
http://hammett.castleproject.org/
--
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] Finding subarray
could you please point to some similar
I just want to validate the approach which I am thinking of.
Sent from my iPhone
On Mar 31, 2011, at 0:59, hammett hamm...@gmail.com wrote:
We did :-) Dynamic programming seems as the best way to approach this
kind of problem.
On Wed, Mar 30, 2011 at 12:56 AM, Subhransu
subhransu.panigr...@gmail.com wrote:
For this X = {-1,4,2,3}
Nearest will be 4 then remain is 1 but the there is no 1 so again in
recursion nearest number is 2 then it search for suitable number where the
sum is zero so 3 is not suitable then it will pick the next closest number
to 2 which is one and make it (5= 4 + 2 -1 )
I just propose one approach you guys also can think a better one.
Subhransu Panigrahi
Mobile: +91-9840931538
Email: subhransu.panigr...@gmail.com
On Wed, Mar 30, 2011 at 12:55 PM, Saikat Debnath crazysai...@gmail.com
wrote:
@ Subhranshu : Your approach will fail for a case let X = {-1,4,2,3} and
your sum is 5. You will get nearest element 4, but there is no 1 in the set.
A DP solution will be like this :
Let a[i][j] be the 1 if using the first i elements we can get sum of j,
and 0 otherwise. Initialise a[0][j] = 0, a[i][0] = 1;
Now a[i][j] = a[i-1][j] | a[i-1][ j - X[i] ], where X[i] is ith element of
set X.
On Wed, Mar 30, 2011 at 12:35 PM, hammett hamm...@gmail.com wrote:
I'd try a tabular approach. Check dynamic programming. Samples like
LCS may give you a click.
On Tue, Mar 29, 2011 at 11:46 PM, Subhransu
subhransu.panigr...@gmail.com wrote:
set of integers in an array X that the sum equals a given number N
Eg. X = {-1, -3, 5, 13, 2, 24, 9, 3, 3}
Lets say the number 5 which can be formed in the following manner 5= 2
+ 3
(the values from array). If there is no match it has to return
invalid numbers.
We also have to see the complexity of the solution.
I thought of one approach but not sure if there is more approach where
the
complexity will be minimal.
Lets say sort the array and now take number and find the closest number
for
that.
Then in a recursion manner search for another( Lets say number '5', it
search the list and found closest match
will be 3. Then recursively search for 3 now where closest match is 2)
Any algo with better complexity will be appreciated.
Subhransu Panigrahi
Email: subhransu.panigr...@gmail.com
--
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.
--
Cheers,
hammett
http://hammett.castleproject.org/
--
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.
--
Cheers,
hammett
http://hammett.castleproject.org/
--
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.
