@vicky can yo explain the logic behind the 'Sum Array' computation (if possible elaborately )?
On Sun, Aug 12, 2012 at 8:19 PM, ~*~VICKY~*~ <venkat.jun...@gmail.com>wrote: > Lets build the array for the example you gave. > > i/p: > > 0 1 2 3 > 4 5 6 7 > 8 9 10 11 > > (x1,y1) = (0,0) > (x2,y2) = (1,2) > sumArray > 0 1 2 3 > 4 10 18 28 > 12 27 45 66 > (will take O(n^2) to build above array) > So now when you get coordinates as input, you can calc the sum by > > Ans = sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1] > > For our case it will be Ans = 18-0+0 = 18 > > Please lemme know if any bugs with the logic. > > > On Sun, Aug 12, 2012 at 6:27 PM, Srividhya Sampath <srisam261...@gmail.com > > wrote: > >> >> @ Vicky >> >> Can yo explain with an illustration ? >> >> >> On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ <venkat.jun...@gmail.com>wrote: >> >>> May be you can consider creating a 2d array to pre process and store all >>> the rectangle sums as a dependent subproblem, the sum of larger rect will >>> be currValuesAdded+OldRectSum. So when you get the coordinate as input u >>> can calc the needed sum by subtracting sum of big rect and small rect which >>> is not included in the given coordinates. This can be called constant time >>> if u don't include the preprocessing time. >>> >>> >>> On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar <algog...@gmail.com>wrote: >>> >>>> Sum of the integers meaning? Do you mind giving an example test case? >>>> >>>> regards. >>>> >>>> On Sat, Aug 11, 2012 at 7:10 PM, Srividhya <srisam261...@gmail.com>wrote: >>>> >>>>> hi all:) >>>>> >>>>> The coordinates of a rectangle will be specified. there is a matrix of >>>>> integers. yo should find the sum of the integers that fall in the region >>>>> specified by the coordinates . >>>>> >>>>> The solution to be in constant time . >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Algorithm Geeks" group. >>>>> To view this discussion on the web visit >>>>> https://groups.google.com/d/msg/algogeeks/-/qHSmXBshmS4J. >>>>> 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, >>> >>> Vicky >>> >>> -- >>> 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, > > Vicky > > -- > 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.