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.
