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.com>wrote:
> 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
>>> >> 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.
>>>
>>>
>>
>>
>> --
>> Arpit Bhatnagar
>> (MNIT JAIPUR)
>>
>> --
>> 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.
>
--
regards,
chinna.
--
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.
