@Priyanka ...Do the elements of the subarray need to be continuous ..The
example considers it continuous but still just for clarity ?
On Tue, Jan 10, 2012 at 12:50 AM, surender sanke wrote:
> using extra space of O(n) we can do it in O(n^2)
> take an array for storing cumulative sums from index i
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,
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)
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 wrote:
> I didnt ge
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 B
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 ju
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 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, S
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
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 n
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 pro
@ 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,
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
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
11 matches
Mail list logo
