@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.
