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.
