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
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,
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),
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
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
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
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
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
@ 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,
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
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
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
12 matches
Mail list logo
