@atul if its sum of numbers lesser than a[i] in left to i, then still i think it can be solved in O(nlgn) using Balanced Tree structures ie: if we use AVL tree, then we just need a little care of how to update sum stored with rotations and required ans for ith index must be calculated just after the ith insertion
and if its sum of numbers lesser than i, then first sort(val, index pair) the array and find the prefix sum array would do, with some care for duplicates On Mon, Mar 12, 2012 at 11:09 PM, atul anand <atul.87fri...@gmail.com>wrote: > @sunny : it was a reply to different question. > using AVL or RB for the given algo may screw it. > > > On Mon, Mar 12, 2012 at 11:00 PM, sunny agrawal > <sunny816.i...@gmail.com>wrote: > >> @atul >> TC can be bound to O(nlgn) using any balanced tree ie: AVL tree, RB tree >> as already mentioned in her last post >> >> On Mon, Mar 12, 2012 at 10:44 PM, atul anand <atul.87fri...@gmail.com>wrote: >> >>> @payal: >>> TC will not alwayz be O(nlogn) bcozz we are not sure if the tree formed >>> is balanced. >>> so worst would be O(n^2) >>> >>> >>> On Mon, Mar 12, 2012 at 9:16 PM, payal gupta <gpt.pa...@gmail.com>wrote: >>> >>>> @atul... >>>> if its the sum of the elements to the left of a[i] which are smaller >>>> the my approach works w/o any flaw.... >>>> here's the working code for it....http://ideone.com/CH7VW >>>> if its the sum of all elements lesser than the element a[i] then this >>>> algo is surely wrong >>>> n we then have to proceed by the avl trees or some height balanced tree >>>> n the algo would be of TC-O(nlogn) >>>> btw nyc catch thnx... >>>> >>>> Regards, >>>> PAYAL GUPTA >>>> >>>> >>>> >>>> On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor <pkjee2...@gmail.com>wrote: >>>> >>>>> 1)First map the array numbers into the position in which they would >>>>> be, if they are sorted,for example >>>>> {30,50,10,60,77,88} ---> {2,3,1,4,5,6} >>>>> 2)Now for each number ,find the cumulative frequency of index ( = the >>>>> corresponding number in the map - 1). >>>>> 3)Output the cumulative frequency and increase the frequency at the >>>>> position (=the corresponding number in the map) by the number itself. >>>>> Example >>>>> {3,5,1,6,7,8} Map of which would be {2,3,1,4,5,6} >>>>> Process the numbers now, >>>>> 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is >>>>> 0. so output 0 >>>>> Increase the frequency at index 2 to the number 3. >>>>> 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3. >>>>> Increase the frequency at index 3 to the number 5. >>>>> 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at >>>>> position 1 by 1. >>>>> Similarly for others. >>>>> >>>>> >>>>> -- >>>>> 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. >>> >> >> >> >> -- >> Sunny Aggrawal >> B.Tech. V year,CSI >> Indian Institute Of Technology,Roorkee >> >> -- >> 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. > -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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.
