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.
