Hey I just gave an idea, I believe solve it yourself :) I appreciate your effort.
On Tue, Aug 14, 2012 at 4:34 PM, Kailash Bagaria <kbkailashbaga...@gmail.com > wrote: > @vicky > your approach doesn't work for (x1,y1) = (1,2) > (x2,y2) = (2,3) > > By your Approach:- > Ans= sumArray[x2][y2] - sumArray[x1][y1] + > ip[x1][y1]=66-18+6=*54* > But Actual Ans is 6+7+10+11=*34* > > 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. >> > > > > -- > > -- > > ‘Kailash Bagaria’ > B-tech 4th year > Computer Science & Engineering > Indian Institute of Technology, Roorkee > Roorkee, India (247667) > > -- > 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.
