No, even if they are unsorted still it will be the same b'cos we check for i>V[j] for the second loop.
On Sat, Jun 19, 2010 at 8:41 PM, Chakravarthi Muppalla <chakri...@gmail.com>wrote: > O(S +n ) only when the denominations are in sorted order.isn't it? > > > On Sun, Jun 20, 2010 at 8:41 AM, Anand <anandut2...@gmail.com> wrote: > >> Complexity will be O(S+n) S = Sum required N = Number of denominations >> >> On Sat, Jun 19, 2010 at 12:48 PM, Chakravarthi Muppalla < >> chakri...@gmail.com> wrote: >> >>> Hi anand, >>> could you please enlighten on the running time of the code? >>> >>> >>> On Sun, Jun 20, 2010 at 1:12 AM, Anand <anandut2...@gmail.com> wrote: >>> >>>> Here is my approach for solving this problem using DP. >>>> >>>> http://codepad.org/Op41weg5 >>>> >>>> <http://codepad.org/Op41weg5> >>>> >>>> On Thu, Jun 17, 2010 at 6:33 AM, Chakravarthi Muppalla < >>>> chakri...@gmail.com> wrote: >>>> >>>>> I think that we need to go by dynamic programming. >>>>> Ex: 1,3,7,4,9 T=23 >>>>> Sort: 1,3,4,7,9 >>>>> subtract max value from T(23-9=14 ) >>>>> find Best Solution for (14) --> sub (14-9 = 5), Search for 5.(5-4 = 1) >>>>> So Answer would be: 9,9,4,1 >>>>> Search can be binary search as the array is already sorted. >>>>> At every step best solution for the specified number could be saved in >>>>> a hash table for any further references. >>>>> >>>>> >>>>> Thanks & Regards, >>>>> Chakravarthi. >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> On Thu, Jun 17, 2010 at 6:10 PM, Rohit Saraf < >>>>> rohit.kumar.sa...@gmail.com> wrote: >>>>> >>>>>> Yes right, i forgot the "1" >>>>>> >>>>>> -------------------------------------------------- >>>>>> Rohit Saraf >>>>>> Second Year Undergraduate, >>>>>> Dept. of Computer Science and Engineering >>>>>> IIT Bombay >>>>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>> >>>>>> >>>>>> On Thu, Jun 17, 2010 at 6:05 PM, Dave <dave_and_da...@juno.com>wrote: >>>>>> >>>>>>> No. The greedy algorithm also works on the U.S. coinage system, where >>>>>>> the coins are 1, 5, 10, 25. Again, the rule is that there must be a 1 >>>>>>> unit coin, and each coin has at least twice the value of the >>>>>>> preceeding one. >>>>>>> >>>>>>> Dave >>>>>>> >>>>>>> On Jun 16, 11:34 pm, Rohit Saraf <rohit.kumar.sa...@gmail.com> >>>>>>> wrote: >>>>>>> > @Dave: The greedy will only work if the coins are k,2k,3k,4k,.... >>>>>>> nk without >>>>>>> > any of these missing >>>>>>> > Clear? >>>>>>> > (Perhaps i did not write it clearly as i was on mobile) >>>>>>> > -------------------------------------------------- >>>>>>> > Rohit Saraf >>>>>>> > Second Year Undergraduate, >>>>>>> > Dept. of Computer Science and Engineering >>>>>>> > IIT >>>>>>> > Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>>> > >>>>>>> > >>>>>>> > >>>>>>> > On Thu, Jun 17, 2010 at 10:00 AM, Dave <dave_and_da...@juno.com> >>>>>>> wrote: >>>>>>> > > The greedy algorithm doesn't work, e.g., when the coins are 1, 5, >>>>>>> and >>>>>>> > > 8 units, and you want to make 15 units. In this case, the greedy >>>>>>> > > algorithm would choose 8, 5, 1, 1, whereas the optimal is 5, 5, >>>>>>> 5. I >>>>>>> > > believe the criterion for the greedy algorithm are that the >>>>>>> smallest >>>>>>> > > coin be 1 unit and each successive coin be at least twice the >>>>>>> value of >>>>>>> > > its predecessor. >>>>>>> > >>>>>>> > > Dave >>>>>>> > >>>>>>> > > On Jun 16, 9:19 pm, Rohit Saraf <rohit.kumar.sa...@gmail.com> >>>>>>> wrote: >>>>>>> > > > If the coins are all multiple of some number k, you can >>>>>>> greedily give >>>>>>> > > > as much as possible to the higher domination. Otherwise still, >>>>>>> there >>>>>>> > > > is an optimal substructure and u can make a recurrence and use >>>>>>> > > > memoization(i.e. DP) >>>>>>> > >>>>>>> > > > -- >>>>>>> > > > -------------------------------------------------- >>>>>>> > > > Rohit Saraf >>>>>>> > > > Second Year Undergraduate, >>>>>>> > > > Dept. of Computer Science and Engineering >>>>>>> > > > IIT >>>>>>> > > > Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>>> > >>>>>>> > > -- >>>>>>> > > You received this message because you are subscribed to the >>>>>>> Google Groups >>>>>>> > > "Algorithm Geeks" group. >>>>>>> > > To post to this group, send email to algoge...@googlegroups.com. >>>>>>> > > To unsubscribe from this group, send email to >>>>>>> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>>>> <algogeeks%2bunsubscr...@googlegroups.com> >>>>>>> > > . >>>>>>> > > For more options, visit this group at >>>>>>> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text >>>>>>> - >>>>>>> > >>>>>>> > - Show quoted text - >>>>>>> >>>>>>> -- >>>>>>> You received this message because you are subscribed to the Google >>>>>>> Groups "Algorithm Geeks" group. >>>>>>> To post to this group, send email to algoge...@googlegroups.com. >>>>>>> To unsubscribe from this group, send email to >>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >>>>>> To unsubscribe from this group, send email to >>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>>> . >>>>>> For more options, visit this group at >>>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> Thanks, >>>>> Chakravarthi. >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Algorithm Geeks" group. >>>>> To post to this group, send email to algoge...@googlegroups.com. >>>>> To unsubscribe from this group, send email to >>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> >>> >>> -- >>> Thanks, >>> Chakravarthi. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Thanks, > Chakravarthi. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
